Why checking an answer can be easier than finding one

A finished jigsaw is obviously solved; a box of pieces may take days. Many problems share this shape: a proposed answer is quick to check, but nobody knows a quick way to find one. Whether that gap is real or only a gap in our knowledge is the P versus NP question — and it is open.

Two kinds of "easy"

Aaronson's survey opens with examples sharing two features: "a finite but exponentially-large space of possible solutions" and "a fast, mechanical way to check whether any claimed solution is 'valid.'" Checking is mechanical; finding is the work. The question is whether there is "a general method to find a valid solution whenever one exists" that is "enormously faster than just trying all the possibilities one by one."

Why it matters

The survey's first stake is cryptography: a decryption key is a search problem whose answer we know how to check, so "essentially all the cryptography that we currently use on the Internet" would be broken if P = NP and the algorithm were practical. The same shape appears in scheduling, fitting a neural network's weights, and searching for a bounded-length formal proof.

Making "fast" and "checkable" precise

"Fast" means polynomial time: steps bounded by the input length raised to some fixed power — n², n³ — rather than growing like 2ⁿ. P is the class of yes-or-no problems a standard computer can solve in polynomial time. NP is the class for which, whenever the answer is yes, there is a polynomial-size witness that a polynomial-time verifier can confirm. Above, the witness is the answer.

The board in the widget is the survey's SubsetSum: is there a subset of the given positive integers summing to the target? Checking a claimed subset is one pass of addition. The widget's only way to find one is to try subsets, and n numbers give 2ⁿ of them. Every P problem is in NP, because a verifier can ignore the witness and solve the problem itself. The question is whether the containment is proper — as the survey puts it, "The central conjecture is that this containment is strict."

What is and is not known

The rule this page turns on: the widget's counter doubling with every added number shows only that brute force is exponential — nothing about whether a cleverer method exists. SubsetSum is among the problems Karp proved NP-complete: if any one of them has a polynomial-time algorithm, then P = NP and all of them do; if any one does not, P ≠ NP. So a method that solves SubsetSum in general — for any numbers, however many digits they carry — would settle the whole question. Nobody has one — but nobody has proved there is none. Aaronson writes that P ≠ NP is what "most computer scientists believe," and argues it is "reasonable to conjecture" it is "both true and provable." He also says that if progress means "having a solution already in sight, or being able to estimate the time to a solution, I know of no progress of that kind." Even that sets up his real point: progress of a different kind — the barriers and lower bounds that explain why the problem is hard — has been real. The larger chain P ⊆ NP ⊆ PH ⊆ PSPACE fares the same: "none of these containments have been proved to be strict."

In short

P is what can be solved quickly; NP is what can be checked quickly once handed the answer. For hundreds of practical problems, checking is fast and the best known worst-case finding methods are exponential. Whether that is because no fast way exists, or because none has been found, is exactly what is not known.