Worth a Million Dollars

Checking a completed sudoku takes seconds: verify each row, column and box. Solving one from scratch is a different experience.

Is that difference fundamental, or have we simply not found the right method?

That is P versus NP, stated informally. P is the class of problems solvable in time that grows polynomially with the input size: practical, in the sense that doubling the input multiplies the work by a constant factor. NP is the class where a proposed solution can be checked in polynomial time. Every problem in P is in NP, since solving it is one way to check it. The question is whether the reverse holds.

Almost everybody expects it does not. Nobody has proved it, and the Clay Mathematics Institute offers a million dollars for either answer.

What makes the question tractable to think about is a structural result that is genuinely surprising.

Cook and Levin showed independently around 1971 that the boolean satisfiability problem has a remarkable property: every problem in NP can be translated into it efficiently. Solve satisfiability quickly and you solve everything in NP quickly.

Thousands of problems have since been shown to have the same property by reduction, scheduling, routing, graph colouring, protein folding, timetabling, packing. They are all, in a precise sense, the same problem in different clothing. Find an efficient algorithm for any one and you have found it for all of them.

This is enormously useful in practice even without a resolution. Proving your problem is NP-complete tells you to stop looking for an exact efficient algorithm, because if one existed somebody would almost certainly have found it via one of the thousands of equivalent formulations that people have been attacking for fifty years.

What would it mean if P equalled NP? Considerably more than faster software.

Public-key cryptography would collapse immediately, since it rests on problems being easy in one direction and hard in reverse. Nearly every optimisation problem (logistics, chip design, drug discovery, protein structure) would become tractable. And, as Scott Aaronson has observed, mathematical proof itself would be affected: verifying a proof is easy, so if finding a solution were never much harder than checking one, finding proofs would become mechanical.

That last implication is part of why most researchers expect the answer is no. A world in which creativity is a search problem with an efficient algorithm does not look like this one.

Two cautions, because the complexity classes are routinely over-read.

The first: worst-case hardness says almost nothing about the instances you will actually meet. Modern SAT solvers routinely handle industrial problems with millions of variables. Travelling salesman instances with tens of thousands of cities have been solved to proven optimality. NP-hard means no algorithm is fast on every input, which is a much weaker claim than no algorithm is fast on your input, and real instances have structure that adversarially constructed worst cases do not.

The second: for an engineering team, discovering that a problem is NP-hard is useful information rather than a dead end. It redirects effort away from an exact general algorithm and toward approximation, heuristics and exploiting the structure of the particular problem. A route 2% above optimal computed in a second is almost always worth more than an optimal route computed in a week.

There is one place where the hardness is doing load-bearing work, and it is worth knowing how load-bearing.

RSA encryption rests on the belief that factoring the product of two large primes is infeasible. Multiplying them is trivial; recovering them is not, at sufficient size.

Note the word belief. There is no proof that factoring is hard. It is not even known to be NP-complete, and is suspected to sit somewhere between P and NP-complete. The security of a very large fraction of the internet rests on a conjecture that has resisted attack for decades rather than on a theorem.

And Peter Shor showed in 1994 that a sufficiently large quantum computer could factor efficiently, which would break it. No such machine exists yet and the engineering is extremely hard, and the standardisation of post-quantum cryptography is well under way, because encrypted traffic recorded today can be decrypted later, which means the deadline for switching is not when the machine arrives but well before.