The Hardest Problems Are One Problem

Start with a distinction that sounds trivial and is the whole subject.

Some problems are easy to check and appear hard to solve. Give me a proposed timetable and I can verify in a few minutes that no lecturer is double-booked. Finding a valid timetable from scratch is a different experience entirely. Give me a proposed route through forty cities and I can add up its length; finding the shortest one is not something you do by adding things up.

The class of problems whose proposed answers can be checked quickly is called NP. The class that can also be solved quickly is called P. Whether these are the same class is the open question.

In 1971 Stephen Cook published a result that changed the shape of the field, and Leonid Levin proved essentially the same thing independently in the Soviet Union. What they showed is that every problem in NP can be converted, efficiently, into a single specific problem: satisfiability, which asks whether a logical formula can be made true by some assignment of true and false to its variables.

Converted efficiently means there is a fast procedure that takes any instance of your problem and produces a logical formula which is satisfiable exactly when your instance has a solution. So a fast method for satisfiability would give you a fast method for everything in NP, by translation.

In 1972 Richard Karp did the thing that made this famous. He observed that reductions compose: if your problem converts into mine and mine converts into satisfiability, then yours converts into satisfiability. So you never have to repeat Cook's hard general argument. You only have to reduce from one problem already known to be in this position. Karp's paper walks a tree of such reductions and lands twenty-one familiar problems in one go.

The list kept growing and now runs to thousands.

Here is the part that is genuinely strange, and it is worth sitting with rather than nodding at.

Scheduling lectures. Colouring a map so neighbouring regions differ. Packing boxes into a lorry. Routing a delivery van. Deciding whether a circuit can be made to output true. Choosing a set of items within a weight limit. These come from timetabling, cartography, logistics, electrical engineering and operations research. They were studied by people who did not read each other's journals. They have nothing in common on their faces.

They are the same problem. Not analogous, not similar in spirit: the same, in the precise sense that an efficient method for any one of them is an efficient method for all of them, by a translation somebody has already written down.

Which is why the open question carries the weight it does. P versus NP is one of the Clay Millennium problems, with a million-dollar prize attached, and the prize is the least interesting thing about it. A proof that P equals NP, if it were constructive, would not deliver one algorithm. It would dissolve several thousand problems simultaneously, break public-key cryptography, and make a number of professions substantially easier overnight.

Most working opinion expects the answer to be no. Fifty years of extremely capable people failing to find an efficient method for any of these is weak evidence, and weak evidence is what there is. Nobody can prove it, and the techniques that have been tried have mostly been shown, in a precise sense, to be incapable of settling it.

So the situation is: thousands of problems, one question, no proof, and an entire industry of cryptography quietly resting on the expectation that the answer is the one everybody believes.