P versus NP problem

The P versus NP problem is a major unsolved problem in theoretical computer science that asks whether every problem whose solution can be quickly verified by a computer (NP) can also be quickly solved by a computer (P). It was formally introduced in 1971 by Stephen Cook and, independently, by Leonid Levin, and is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, with a US$1,000,000 prize for a correct solution.

Informal description

Consider two types of computational tasks. A problem is in P (polynomial time) if there exists an algorithm that, for any input of size \(n\), finds a solution in time bounded by a polynomial in \(n\). Examples include sorting a list, searching a database, and computing the greatest common divisor. In contrast, a problem is in NP (nondeterministic polynomial time) if a proposed solution can be checked for correctness in polynomial time; the proposal itself may be produced by a nondeterministic process or by an all‑powerful oracle. The classic example is the Boolean satisfiability problem (SAT): given a Boolean formula, it is easy to verify whether a particular assignment of variables makes the formula true, but finding such an assignment among all \(2^n\) possibilities appears to require exponential time in the worst case.

The question “P = NP?” thus asks: if a solution can be verified efficiently, can it also be found efficiently? Because every problem in P is trivially in NP (the verification step can simply rerun the solver), the central question is whether NP is a strictly larger class than P.

Formal definitions

Let a deterministic Turing machine be a standard model of computation. The class P consists of all decision problems (problems with a yes/no answer) for which there exists a deterministic Turing machine that decides the problem in time \(O(n^k)\) for some constant \(k\), where \(n\) is the input size.

The class NP consists of all decision problems for which a “yes” instance has a certificate that can be verified in polynomial time by a deterministic Turing machine. Equivalently, NP is the set of decision problems solvable by a nondeterministic Turing machine in polynomial time. The nondeterministic machine can “guess” a certificate and then verify it, and it accepts if some guess leads to acceptance.

Both classes are defined with respect to decision problems, but the question naturally extends to search problems and optimization problems through standard polynomial‑time reductions.

History

The distinction between finding and verifying solutions was implicit in the work of many pioneers of computing. In a 1956 letter, Kurt Gödel asked John von Neumann whether a certain problem (propositional proofs) could be solved in polynomial time. The modern formulation emerged in the early 1970s. In 1971, Stephen Cook published his seminal paper “The Complexity of Theorem‑Proving Procedures,” which introduced the concept of NP‑completeness and proved that the Boolean satisfiability problem (SAT) is NP‑complete. Independently, Leonid Levin arrived at similar notions in the Soviet Union, defining “universal search problems.” Shortly afterward, Richard Karp demonstrated that 21 well‑known combinatorial problems (including the traveling salesman decision problem, clique, and set cover) are NP‑complete, solidifying the central role of P versus NP.

The problem became widely recognized as one of the most important open questions in computer science and mathematics. In 2000, the Clay Mathematics Institute designated it as a Millennium Prize Problem.

NP‑completeness

A decision problem \(A\) is NP‑hard if every problem in NP can be reduced to \(A\) by a polynomial‑time many‑one reduction (or another appropriate reduction). If, in addition, \(A\) is itself in NP, then \(A\) is NP‑complete. The Cook–Levin theorem establishes that SAT is NP‑complete, giving the first example of such a problem.

The significance of NP‑completeness is that if any NP‑complete problem can be solved in polynomial time, then \(P = NP\). Conversely, if \(P \neq NP\), no NP‑complete problem can be in P. Thousands of problems across mathematics, science, and engineering have been shown to be NP‑complete, including the traveling salesman decision problem, graph coloring, integer programming, and many scheduling and packing problems.

Importance

The P versus NP question lies at the heart of our understanding of efficient computation. Its resolution would have profound implications:

• Theoretical computer science: A proof that \(P = NP\) would mean that the creative act of finding a solution is no more difficult than checking one, reshaping our view of computation and intelligence. A proof that \(P \neq NP\) would confirm the existence of intrinsically hard search problems.
• Cryptography: Modern cryptographic systems (e.g., RSA, AES) rely on the assumption that certain problems, such as integer factorization, are hard. While factorization is not known to be NP‑complete, many cryptographic protocols are based on NP‑hard problems. If \(P = NP\), most public‑key cryptography would collapse, as breaking encryption would become efficiently solvable.
• Optimization and operations research: Vast numbers of industrial optimization problems are NP‑hard. An efficient algorithm for an NP‑complete problem would enable exact solutions to previously intractable tasks in logistics, manufacturing, and resource allocation.
• Mathematics and science: Automated theorem proving, protein folding, and many other scientific challenges involve NP‑hard problems. A positive answer could revolutionize these fields.

Even a proof that \(P \neq NP\) would have practical consequences: it would validate the search for heuristic, approximation, and exponential‑time algorithms that currently dominate practice.

Barriers to proof

Despite decades of effort, the problem remains open. Research has revealed deep barriers that prevent many natural proof strategies from succeeding.

• Relativization (Baker, Gill, and Solovay, 1975): There exist oracles (external computational aids) relative to which \(P = NP\) and other oracles relative to which \(P \neq NP\). Any proof that resolves P versus NP without relativizing assumptions (i.e., a proof that would work relative to every oracle) cannot exist, because it would have to give contradictory results in different relativized worlds. Most standard diagonalization arguments relativize, so this result shows that new techniques are needed.

• Natural proofs (Razborov and Rudich, 1994): A natural proof is a certain kind of combinatorial argument that would separate complexity classes under widely believed cryptographic assumptions. Razborov and Rudich showed that if one‑way functions exist, no natural proof can show that \(P \neq NP\). This rules out many circuit‑lower‑bound approaches that evaluate a function on random inputs and detect a “hard” property.

• Algebraization (Aaronson and Wigderson, 2009): Even techniques that extend relativization by adding algebraic oracles (such as the technique used to prove IP = PSPACE) cannot resolve P versus NP. The algebraization barrier shows that further novel ideas are required.

These barriers indicate that the problem is not only unsolved, but also remarkably resistant to a wide range of attack methods.

Approaches and related results

Researchers have pursued numerous lines of attack that, while not resolving the main question, have advanced complexity theory.

• Circuit complexity: Proving superpolynomial lower bounds on the size of Boolean circuits for an NP‑complete problem would imply \(P \neq NP\). Significant progress has been made in restricted circuit models (e.g., constant‑depth circuits, monotone circuits), but general circuit lower bounds remain elusive.

• Proof complexity: This area studies the lengths of proofs in formal systems. If arbitrarily strong propositional proof systems require superpolynomial proof lengths for the pigeonhole principle or similar tautologies, then \(P \neq NP\). While exponential lower bounds have been shown for weak proof systems, the main conjecture is open.

• Derandomization: Under plausible hardness assumptions, it is known that P = BPP (randomized polynomial time can be simulated deterministically). The connection between derandomization and circuit lower bounds suggests that proving strong circuit lower bounds would yield derandomization results, but the converse has also been partially established.

• Interactive proofs and probabilistically checkable proofs (PCPs): The result IP = PSPACE and the PCP theorem have revolutionized our understanding of verification. They show that interactive and probabilistic verification can be far more powerful than static certificates, but they have not settled the P versus NP question. The PCP theorem implies that certain approximation problems are NP‑hard, linking hardness of approximation to the original question.

• Algebraic and geometric methods: Approaches based on algebraic geometry, representation theory, and other advanced mathematics have been proposed (e.g., Mulmuley and Sohoni’s Geometric Complexity Theory). These approaches aim to use symmetry to separate algebraic variants of P and NP and are still under active investigation.

Consequences of a resolution

If \(P = NP\):

• All NP problems, including NP‑complete ones, would have polynomial‑time algorithms. However, the polynomial degrees could be impractically large (e.g., \(O(n^{100})\)), limiting immediate practical impact.
• Cryptography based on worst‑case NP‑hardness would be broken; security would need to be rebuilt from average‑case complexity or information‑theoretic principles.
• The polynomial hierarchy would collapse to its first level (PH = P).
• Many tasks in artificial intelligence and automated reasoning would become theoretically tractable, though heuristic methods might still dominate.

If \(P \neq NP\):

• There would be no polynomial‑time algorithm for NP‑complete problems, confirming the widely believed inherent difficulty of these problems.
• One‑way functions would likely exist, forming a firm foundation for cryptography (though this link itself is not yet proven: the existence of one‑way functions implies \(P \neq NP\), but the converse is unknown).
• The polynomial hierarchy would be infinite.
• Approximation and heuristic algorithms would remain essential for practical problem solving.

Related complexity classes

Several classes are intimately linked to the P versus NP question:

• co‑NP: The complement class of NP. It is known that P ⊆ NP ∩ co‑NP, but whether NP = co‑NP is also unknown. If \(P = NP\), then NP = co‑NP.
• NP‑hard and NP‑complete: As described, the status of these classes depends on the answer.
• #P: The counting version of NP, which asks how many solutions exist. The problem of computing the permanent of a {0,1}‑matrix is #P‑complete.
• Polynomial hierarchy (PH): An infinite hierarchy of complexity classes that generalize P and NP. If \(P = NP\), the entire hierarchy collapses.
• BPP and RP: Randomized classes that are believed to equal P, but a proof would require separating P from NP or making other breakthroughs.

Current status

The Clay Mathematics Institute added the P versus NP problem to its list of Millennium Prize Problems in 2000. Despite sustained attention from leading mathematicians and computer scientists and a few published attempts that were later shown to contain errors, the question remains wide open. Most researchers believe \(P \neq NP\), but a consensus is not universal, and the formal proof remains one of the deepest challenges in modern science.