P versus NP problem

Lore & Background

The P versus NP problem asks whether every decision problem whose positive answer can be verified quickly can also be solved quickly, where "quickly" means in polynomial time—time bounded by a polynomial function of the input size. The class P contains problems solvable in polynomial time on a deterministic sequential computer. The class NP contains problems whose positive solutions can be verified in polynomial time, given the right information; equivalently, they can be solved in polynomial time on a nondeterministic machine. The problem is a major unsolved question in theoretical computer science and is one of the seven Millennium Prize Problems, each carrying a US$1,000,000 prize. It was formally defined in 1971 by Stephen Cook and independently by Leonid Levin in 1973. Earlier inklings appeared in a 1955 letter from John Nash to the National Security Agency, speculating that code-cracking time would grow exponentially with key length, implying P ≠ NP, since a key can be verified in polynomial time. In a 1956 letter, Kurt Gödel asked John von Neumann whether theorem-proving (now known to be co-NP-complete) could be solved in quadratic or linear time, suggesting automated proof discovery. A proof either way would profoundly impact mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, and economics. Surveys by William Gasarch in 2001, 2011, and 2018 show that the share of researchers believing P ≠ NP rose from 61% to 88%, with 99% of experts in 2018 holding that view. The concept of NP-completeness is key: NP-complete problems are those to which any NP problem can be reduced in polynomial time, and their solution remains verifiable in polynomial time.

Reader's Guide

The P versus NP problem is central to computational complexity theory, which studies the resources required during computation to solve a given problem. The class P consists of decision problems solvable on a deterministic sequential machine in polynomial time; the class NP consists of problems whose positive solutions are verifiable in polynomial time. An answer to the question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If P ≠ NP, which is widely believed, it would mean there are problems in NP that are harder to compute than to verify. A proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics, and many other fields. The concept of NP-completeness is useful in attacking the question: NP-complete problems are those that any other NP problem can be reduced to in polynomial time, and if any NP-complete problem is in P, then P = NP. The Boolean satisfiability problem was the first natural problem proven to be NP-complete by the Cook–Levin theorem.

Did You Know?

• Generalized Sudoku is in NP (quickly verifiable) but may or may not be in P (quickly solvable).

Two Faces of the Same Class

NP can be understood through two equivalent lenses. One view frames it as the collection of decision problems a nondeterministic Turing machine can resolve within polynomial time—hence the name "nondeterministic polynomial time." The other, equally valid perspective describes NP as the set of problems where a "yes" answer comes with a proof that a deterministic machine can check in polynomial time. These two descriptions are not merely parallel; they are mathematically interchangeable. The reason lies in the structure of the underlying algorithm: it unfolds in two phases. First, a candidate solution is produced through a nondeterministic guess. Second, a deterministic procedure confirms whether that guess actually solves the instance. Because the guessing step can be reinterpreted as the existence of a suitable witness string, and the checking step is purely deterministic, the machine-based and verifier-based characterizations collapse into one another. This duality gives researchers flexibility: they can reason about NP either in terms of hypothetical parallel exploration or in terms of efficient certification, depending on which angle illuminates the problem at hand.

The Central Question and Its Stakes

The class P, encompassing every decision problem a deterministic machine can solve in polynomial time, sits neatly inside NP. The inclusion is straightforward: if you can solve a problem quickly, you can certainly verify a proposed answer quickly by simply re-solving it. Yet the reverse direction—whether every problem with efficiently checkable solutions also admits an efficient solver—remains one of the deepest open questions in mathematics. The prevailing intuition among complexity theorists is that P is a strict subset of NP, meaning some problems are fundamentally easier to check than to find. At the top of NP sit the NP-complete problems, a family so interconnected that a polynomial-time algorithm for any single member would immediately unlock polynomial-time solutions for every problem in NP. Thus, proving P equals NP would not merely settle one question; it would hand researchers efficient algorithms for an enormous landscape of search and optimization challenges that currently resist them.

A Concrete Window into Verification

The subset sum problem offers a vivid illustration of why NP feels so natural. Given a collection of integers, say {−7, −3, −2, 5, 8}, the question asks whether some subcollection adds to zero. Here the answer is affirmative: {−3, −2, 5} produces the sum zero. Finding such a subset by brute force requires enumerating every possible combination, a task whose cost balloons exponentially as the input grows. Yet if someone hands you a specific subset, confirming that its elements sum to zero is a matter of a single pass of addition—clearly polynomial time. That subset acts as a witness, sometimes called a certificate, and the addition routine serves as the verifier. This pattern generalizes: a decision problem belongs to NP whenever there exists a verifier that, given the problem instance paired with a witness string, returns "yes" in polynomial time when the witness is valid and "no" otherwise. The distinction between the exponential search and the polynomial check is precisely what separates P from NP in the minds of those who study these classes.

The Shadow Class co-NP

Alongside NP stands its mirror image, co-NP. While NP guarantees efficient verification of "yes" answers, co-NP is the class of problems where "no" answers carry efficiently checkable proofs. The subset sum example makes the contrast tangible: asking "does some subset sum to zero?" is an NP question, whereas asking "does every non-empty subset have a nonzero sum?" is its co-NP counterpart. The verifier-based definition of NP deliberately does not demand an efficient certificate for negative answers, which is exactly the gap that co-NP fills. Whether these two classes coincide—whether NP equals co-NP—is an open question that remains unresolved in complexity theory. It is a separate, though related, mystery from the P-versus-NP problem. Together, the unresolved status of P versus NP and NP versus co-NP frames two of the most fundamental boundaries in our understanding of what computation can and cannot do efficiently, and both continue to resist proof despite decades of intensive effort.