The P versus NP problem is probably the most famous open question in theoretical computer science, and it is one of the Millennium Prize Problems chosen by the Clay Mathematics Institute. It can be stated in one line: can every problem whose solution is quickly verified also be quickly solved? Most experts believe the answer is no, but nobody has managed to prove it. It is worth understanding precisely what is being asked, what depends on the answer and why known techniques fall short.
The question in precise form
We know that P ⊆ NP: whatever can be solved in polynomial time can also be verified in polynomial time. The question is whether the inclusion is strict:
P = NP or P ≠ NP?
Thanks to NP-completeness, the question reduces to a single problem. Take SAT, or any other NP-complete problem:
- if SAT has a polynomial algorithm, then P = NP;
- if it is proved that SAT has none, then P ≠ NP.
Scenario 1: P = NP
If P = NP, every problem with quickly verifiable solutions would also have a polynomial algorithm for finding them. The consequences would depend heavily on how it was proved.
- A constructive and efficient proof, with a low-degree algorithm and reasonable constants, would upend practice: many planning, scheduling, circuit design and resource allocation problems would become exactly solvable.
- Public-key cryptography as we know it would lose its foundations. Given a public key, checking that a candidate private key is the right one is easy; with P = NP finding it would be easy too. More generally there would be no one-way functions, that is functions easy to compute and hard to invert.
- Proof search would become mechanizable for proofs of reasonable length: checking a formal proof is easy, so finding one would be too.
But a proof of P = NP might also be non-constructive, or yield an n¹⁰⁰⁰ algorithm. In that case the theoretical result would be enormous, but the immediate practical impact almost nil.
Scenario 2: P ≠ NP
This is the scenario considered more likely. It would confirm what experience suggests: for NP-complete problems there is no efficient algorithm that works on every instance. But here too some care is needed.
- P ≠ NP concerns the worst case. Many industrial SAT instances, even very large ones, are routinely solved by modern solvers. Theoretical hardness does not prevent practical success on structured instances.
- P ≠ NP is not enough for cryptography. Cryptography needs problems that are hard on average, that is on randomly generated instances, not just on a few pathological ones. Assumptions stronger than P ≠ NP are required.
- Other questions would remain open, such as NP versus coNP or P versus PSPACE.
Intermediate problems
If P ≠ NP, is every problem in NP either in P or NP-complete? No. Ladner's theorem proves that, if P ≠ NP, there are problems in NP that are neither in P nor NP-complete: the NP-intermediate problems.
The examples built in the proof are artificial, but there are natural candidates, problems in NP for which neither a polynomial algorithm nor an NP-completeness proof is known:
- integer factoring, in its decision version;
- graph isomorphism: are two given graphs the same graph with the nodes renamed?
- the discrete logarithm.
Factoring and discrete logarithm underlie very widely used cryptographic schemes: their security rests precisely on the fact that nobody knows efficient classical algorithms for them.
Why it is so hard
It is not just a lack of ideas: theorems have been proved that rule out whole families of techniques.
- Relativization. There are oracles A for which P^A = NP^A and oracles B for which P^B ≠ NP^B. Many classical techniques, such as diagonalization, work the same way with any oracle. So on their own they cannot settle the question.
- Natural proofs. A broad class of combinatorial arguments about circuits, if it succeeded in separating P from NP, would also make it possible to break pseudorandom generators believed to be secure. This makes it unlikely that such arguments work.
- Algebrization. An extension of the relativization barrier also rules out algebraic techniques that had enabled other important results.
Any proof of P ≠ NP will therefore need ideas substantially different from those that have succeeded so far.
How the real world lives with the doubt
In everyday work P versus NP is not left as an abstraction. When a problem turns out to be NP-complete, the strategies are well known:
- exploit the structure of real instances, often much simpler than the worst case;
- accept approximate solutions with quality guarantees;
- use heuristics and specialized solvers, measuring their performance on the instances that matter;
- bound a parameter of the problem, such as the size of a solution, when it stays small.
In short
- P versus NP asks whether everything that can be verified quickly can also be solved quickly.
- Settling the question for a single NP-complete problem, such as SAT, is enough.
- P = NP would undermine one-way functions, but the practical impact would depend on the algorithm's efficiency.
- If P ≠ NP, Ladner's theorem guarantees intermediate problems; factoring and graph isomorphism are candidates.
- Relativization, natural proofs and algebrization rule out many known techniques.
