P versus NP problem

The P versus NP problem is the central unsolved question in theoretical computer science and one of the seven Millennium Prize Problems for which the Clay Mathematics Institute offers a US$1,000,000 prize. It asks whether every problem whose solution can be verified quickly (in polynomial time) can also be solved quickly. Formally: does the complexity class P equal the class NP?

The problem was independently formulated by Stephen Cook in 1971 and Leonid Levin in 1973. Cook's seminal paper, "The Complexity of Theorem-Proving Procedures," introduced the notion of NP-completeness and proved that the Boolean satisfiability problem (SAT) is NP-complete — meaning it is at least as hard as any problem in NP. This discovery established a framework that now underpins virtually all of computational complexity theory.

Despite decades of intense effort by hundreds of researchers, the P versus NP question remains open. The overwhelming consensus among computer scientists is that P ≠ NP, but no proof has been accepted. A resolution — in either direction — would have profound consequences for cryptography, optimization, artificial intelligence, scientific computing, and our fundamental understanding of computation itself.

Formal definitions

The complexity class P (polynomial time) consists of all decision problems that can be solved by a deterministic Turing machine in time bounded by a polynomial function of the input size. Intuitively, these are problems that can be solved efficiently — in time that grows reasonably as the input gets larger. Examples include determining whether a number is prime, sorting a list, and finding the shortest path in a graph.

The complexity class NP (nondeterministic polynomial time) consists of all decision problems for which a proposed solution can be verified in polynomial time by a deterministic Turing machine. Equivalently, NP is the set of problems that can be solved in polynomial time by a nondeterministic Turing machine — one that can "guess" the correct answer. Examples include determining whether a Boolean formula has a satisfying assignment (SAT), whether a graph contains a Hamiltonian cycle, and whether an integer has a nontrivial factor.

The question "Does P = NP?" asks whether these two classes are identical. If P = NP, then every problem that can be verified quickly can also be solved quickly — a world where finding proofs is no harder than checking them. If P ≠ NP, then there exist problems in NP that are inherently harder than any problem in P, requiring super-polynomial time to solve in the worst case.

NP-completeness and the Cook-Levin theorem

A problem is called NP-hard if every problem in NP can be reduced to it in polynomial time. An NP-hard problem that is also in NP is called NP-complete. NP-complete problems are the "hardest" problems in NP: if any NP-complete problem can be solved in polynomial time, then every problem in NP can be solved in polynomial time, proving P = NP. Conversely, if any NP-complete problem requires super-polynomial time, then P ≠ NP.

The Cook-Levin theorem (1971–1973) was the first proof of NP-completeness. Cook showed that the Boolean satisfiability problem (SAT) — determining whether a given Boolean formula has an assignment of variables that makes it true — is NP-complete. His proof constructed a polynomial-time reduction from any NP problem to SAT by encoding the computation of a nondeterministic Turing machine as a Boolean formula. Levin independently proved a similar result in the Soviet Union, though his work was less widely known in the West for several years.

Since Cook and Levin's initial result, thousands of problems across mathematics, engineering, biology, physics, and economics have been proven NP-complete. These include the traveling salesman problem (decision version), graph coloring, knapsack, integer programming, and many scheduling problems. The discovery that such a diverse array of practical problems are all computationally equivalent — in the sense that a polynomial-time solution to any one would solve all of them — is one of the most striking findings in the history of computer science.

Major results and barriers

Several landmark results have shaped our understanding of the P versus NP problem, even without resolving it. The Baker-Gill-Solovay theorem (1975) showed that there exist oracles A and B such that P^A = NP^A and P^B ≠ NP^B. This result demonstrated that relativizing proof techniques — those that treat Turing machines with access to an oracle — cannot resolve P versus NP, because the answer depends on the oracle. This is known as the relativization barrier.

The natural proofs barrier, established by Alexander Razborov and Steven Rudich in 1997, showed that a broad class of proof techniques — those that construct a "natural" combinatorial property of Boolean functions that separates P from NP — would also break cryptographic pseudorandom generators, which are widely believed to exist. This means that any proof of P ≠ NP must use non-naturalizing arguments, ruling out many of the most intuitive approaches.

In 2008, Scott Aaronson and Avi Wigderson introduced the algebrization barrier, showing that even non-relativizing techniques that rely on algebraic encodings (such as those used in the proof that IP = PSPACE) are insufficient to separate P from NP. Together, these three barriers — relativization, natural proofs, and algebrization — explain why the problem has resisted attack for over five decades and guide researchers toward the kinds of arguments that might eventually succeed.

Implications of a resolution

If P = NP, the consequences would be revolutionary. Many problems currently considered intractable would become efficiently solvable: optimal logistics and scheduling, protein folding prediction, theorem proving, and the breaking of essentially all public-key cryptography (including RSA and elliptic curve cryptosystems). Machine learning and AI would be transformed, as many learning problems are in NP. However, the proof would likely be non-constructive or involve astronomically large polynomial exponents, so the practical impact might be gradual rather than immediate.

If P ≠ NP (the widely believed outcome), the consequences would be more subtle but no less important. A proof would confirm that many optimization and search problems are fundamentally hard in the worst case, justifying the use of approximation algorithms, heuristics, and exponential-time exact solvers. It would also validate the security of cryptographic systems that rely on the hardness of NP problems, such as factoring and discrete logarithm. A proof of P ≠ NP would be one of the greatest intellectual achievements in mathematics, comparable to the resolution of Fermat's Last Theorem or the Poincaré conjecture.

In 2025, researcher Georgiadis published a claimed proof of P ≠ NP using a novel approach based on the structure of Boolean function composition and the properties of the complexity measure β. The proof has been submitted for peer review and has generated significant discussion in the complexity theory community, though it has not yet been widely accepted. If validated, it would represent the first resolution of the problem in over 50 years.

Connections to other fields

The P versus NP problem has deep connections to philosophy, particularly the nature of creativity and discovery. If P = NP, then finding a proof is no harder than verifying one — suggesting that creativity could, in principle, be automated. If P ≠ NP, then there is a fundamental gap between recognizing a good solution and generating one, which resonates with the philosophical distinction between "knowing that" and "knowing how."

In cryptography, the security of essentially all public-key systems depends on the assumption that certain NP problems (like factoring and discrete logarithm) are not in P. A proof of P = NP would break these systems, while a proof of P ≠ NP would provide theoretical justification for their security — though practical cryptosystems also depend on average-case hardness, not just worst-case hardness.

The problem also connects to physics through the concept of NP-completeness in physical systems. Determining the ground state of certain spin glasses is NP-complete, as is simulating some quantum systems classically. The relationship between quantum computing and the P versus NP question is particularly rich: while quantum computers are believed to solve certain problems (like factoring) faster than classical computers, they are not believed to solve NP-complete problems efficiently — the question of whether BQP (bounded-error quantum polynomial time) contains NP is also open.

Popular culture and significance

The P versus NP problem has entered popular culture as a symbol of intellectual challenge and the limits of computation. It has been featured in television shows (including The Simpsons and Elementary), novels, and films. The problem is often described in lay terms as the question of whether "every problem whose solution can be checked quickly can also be solved quickly" — a framing that captures the intuitive gap between verification and discovery.

The Clay Mathematics Institute designated P versus NP as one of its seven Millennium Prize Problems in 2000, offering a US$1,000,000 prize for a correct solution. The problem is unique among the seven in being primarily a computer science question rather than a pure mathematics one, reflecting the deep interweaving of the two disciplines. As of 2026, only one of the seven Millennium Problems (the Poincaré conjecture, proved by Grigori Perelman) has been resolved.

The broader significance of P versus NP extends beyond any particular application. The problem asks a fundamental question about the nature of efficient computation: are there problems for which finding a solution is inherently harder than verifying one? This question touches on the limits of knowledge, the nature of proof, and the boundary between what is computable in practice and what is computable in principle.

See also

• Computability Theory
• Turing Machine
• Complexity Theory
• Algorithm Analysis
• Cryptography
• Quantum Computing

References

External links

• Clay Mathematics Institute — P vs NP
• Scott Aaronson's Shtetl-Optimized blog
• Complexity Zoo (complexityzoo.net)