Finding is hard. Checking is easy.
A jigsaw takes an afternoon to finish and a second to see that it is finished. A sudoku is work to solve and no work at all to mark. That gap between finding and checking feels obvious. Nobody has been able to prove it is real.
P is the set of questions a computer can answer quickly. NP is the set of questions where, if somebody hands you an answer, you can check it quickly. Every question you can answer quickly you can obviously also check quickly, so P sits inside NP. The question is whether it fills it.
01 | The gap
One grows like a wall. The other barely grows at all.
Take a problem with n parts. Checking a proposed answer usually means walking the parts once or twice, so the work grows like n, or n squared. Searching for the answer by trying everything means walking every combination, and there are two to the power n of those. Both curves start in the same place. Only one of them stays on the page.
- Checking one answer
- ·
- Trying every answer
- ·
- Searching at a billion a second
- ·
The scale is logarithmic: every gridline is a thousand times the one below it. Checking is the flat curve. Searching is the straight line, and a straight line on this scale is an explosion. Nothing about that picture is a proof, though. It shows that the obvious method is hopeless, not that no clever method exists.
02 | A puzzle to feel it on
Pick numbers that add to the target.
Here are fourteen numbers and one target. Somewhere in them is a handful that adds up exactly. Finding it by hand is genuinely annoying. Checking a proposed handful takes thirteen additions, which is why this problem is in NP. Press the search button and watch how many of the sixteen thousand combinations the machine has to walk before it lands on one.
Click numbers to add them up.
Fourteen numbers means 16,384 possible selections. Twenty numbers would be a million, thirty would be a billion, and a hundred numbers would be more selections than there are atoms in the earth. Every one of those puzzles is checked with a single pass of additions.
03 | All one problem
They are all the same problem wearing different clothes.
In 1971 Stephen Cook showed that one problem in NP, satisfiability, is at least as hard as every other problem in NP: any of them can be rewritten as a satisfiability question in a manageable amount of work. Richard Karp then showed twenty-one more problems have the same property. The list is now in the thousands, and it runs through scheduling, routing, protein folding and circuit design.
That is what makes the question worth a million dollars. These problems are not merely similar. They are welded together. A fast method for any single one of them is a fast method for all of them at once.
An arrow means the problem at the tail can be rewritten as the problem at the head, quickly. Follow the arrows backwards and a fast method at any head becomes a fast method for everything behind it. This is why nobody attacks these problems one at a time.
04 | What hangs on it
Two futures, and only one of them is comfortable.
If P does not equal NP, which is what nearly everyone expects, the world stays roughly as it is. Hard problems stay hard, cryptography keeps working because factoring and its relatives stay out of reach, and the value of a good heuristic stays high.
If P equals NP, and the proof came with an actually fast method, almost everything changes at once. Public key cryptography collapses, because breaking a key is exactly a search whose answer is easy to check. So does the distinction between having a proof and finding one: mathematics itself would become, in a sense, a search problem with a fast solution. That second world is so strange that its strangeness is treated as evidence against it.
Neither has been proved. The known barriers are severe: three separate results show that the natural families of proof technique cannot settle the question, which means a proof will have to come from somewhere nobody has looked yet.
Read the definitions
P is the set of decision problems a deterministic machine settles in a number of steps bounded by a polynomial in the input length. NP is the set where a proposed answer, called a certificate, can be verified in polynomial time. NP-complete problems are the hardest in NP: everything in NP reduces to them in polynomial time, so one of them falling into P drags all of NP with it. Note what NP does not stand for: it is nondeterministic polynomial, not non-polynomial.
Behind the visuals
Figure 01 plots log base ten of n squared and of two to the n, so both fit on one axis; the readouts are exact integers up to 2 to the 53 and a decimal exponent above that. Figure 02 holds fourteen fixed numbers and a target that is the sum of a real subset of them. The search button walks the 16,384 selections in counting order and stops at the first that matches, so the count it reports is the honest number of combinations examined, not an estimate. Figure 03 is a drawing, not a computation: the arrows record reductions from Cook's 1971 theorem and Karp's 1972 list.