The P versus NP problem is the central unsolved question of theoretical computer science. Informally: is finding a solution as easy as checking one?
The classes
P is the set of decision problems solvable by a deterministic computer in polynomial time — meaning the running time is bounded by some polynomial in the input size. These are the “efficiently solvable” problems: sorting a list, testing whether a number is prime, finding the shortest path in a graph.
NP is the set of decision problems whose solutions can be verified in polynomial time. Every problem in P is in NP (you can “verify” by solving), but NP may contain much more: problems where finding the answer seems hard, but checking a candidate answer is easy.
A classical example is the Boolean satisfiability problem (SAT): given a Boolean formula, is there an assignment of truth values that makes it true? Checking a candidate assignment takes polynomial time. Finding one appears, in general, to require exponential time.
The question
Does every NP problem also lie in P? Equivalently: is every quickly-verifiable problem also quickly-solvable?
Most computer scientists believe P ≠ NP — that verification is fundamentally easier than discovery. But no one has been able to prove this.
Why it matters
If P = NP were true, the consequences would be immediate and dramatic:
- Public-key cryptography (RSA, elliptic curve, etc.) would collapse
- Thousands of optimization problems currently considered intractable would have efficient solutions
- Much of modern artificial intelligence would become trivial
- Mathematical theorem-proving could potentially be automated
If P ≠ NP, the bound would formally establish the difficulty of a huge class of problems — including ones we encounter in daily computing.
NP-completeness
In 1971, Stephen Cook (and independently in 1973, Leonid Levin) showed that certain NP problems are NP-complete: every other NP problem reduces to them in polynomial time. If any single NP-complete problem could be solved in polynomial time, then all NP problems could.
Thousands of practical problems are NP-complete: traveling salesman, graph coloring, Sudoku, protein folding, scheduling. All of them sit at the same cliff edge.
The prize
P vs NP is one of the seven Millennium Prize Problems with a one-million-dollar reward. It is also often considered the most important open problem in mathematics outside the Riemann hypothesis.
Progress has been made on showing what kinds of proofs cannot work (relativization barriers, natural proof barriers, algebrization barriers), but essentially no positive progress. A proof seems to require fundamentally new techniques.
Frequently asked
What does P = NP actually mean?
P is the class of problems that can be solved by a computer in polynomial time. NP is the class where a proposed solution can be verified in polynomial time. P = NP would mean every quickly-verifiable problem is also quickly-solvable. Most researchers believe P ≠ NP, but no one can prove it.
Why would a proof matter?
If P = NP, nearly every hard computational problem — including those underpinning modern cryptography — would have efficient solutions. Public-key encryption as we know it would collapse. If P ≠ NP (as almost everyone suspects), it would formally establish the inherent difficulty of a huge class of problems.