P vs NP: Checking Is Easy. Is Finding?

Hand someone a filled-in Sudoku grid and ask them to check whether it solves a given puzzle. It’s tedious but quick: scan each row, each column, each 3×3 box, confirm the digits 1–9 each appear once, done. A person can do it in a couple of minutes; a computer does it in microseconds. Now ask that same person to solve the puzzle from a mostly-blank starting grid. Suddenly you’re staring at a search — try a digit, see if it leads anywhere, backtrack, try another. For a standard 9×9 grid it’s merely annoying. But imagine a general $n \times n$ Sudoku, and ask how the effort to solve it grows as $n$ grows, compared to the effort to check a proposed solution. Checking scales gently, roughly like the number of cells. Solving, as far as anyone knows, scales explosively — every known solving method degrades toward trying exponentially many possibilities as $n$ grows, with no shortcut in sight.

This isn’t a Sudoku-specific quirk. Take a completely different problem: subset-sum. Given a list of integers, is there some subset of them that adds up to exactly zero? If someone hands you a candidate subset — say, “use the 3rd, 7th, and 12th numbers” — verifying it is a two-second arithmetic check: add them up, see if you get zero. But finding such a subset, when you don’t know it in advance, seems to require something close to checking all $2^n$ possible subsets in the worst case. Decades of algorithmic effort have produced clever speedups (meet-in-the-middle tricks, dynamic programming that works when the numbers are small), but nothing that tames the worst case into something polynomial.

Factoring large integers has the same shape: multiplying two 1000-digit primes together to check a proposed factorization is fast; finding the two primes from their product, for numbers of that size, is currently beyond the reach of every computer on Earth combined. Checking is cheap. Finding looks expensive. This gap — between the cost of verifying a proposed answer and the cost of finding one — is not an accident of any single puzzle. It’s a pattern that recurs across huge swaths of computing, and asking whether that pattern is a fundamental law of computation or just a failure of imagination is, in essence, the P vs NP question. To ask it precisely, we need to build up some machinery.

Decision problems and the class P

Complexity theory likes to phrase problems as decision problems: questions with a yes/no answer, about inputs encoded as strings of bits. “Is this number prime?” “Does this graph have a path from $s$ to $t$ shorter than $k$?” “Is this Boolean formula satisfiable?” — all yes/no, all defined on inputs of some size $n$ (the number of bits it takes to write the input down).

A decision problem is in the class P (“polynomial time”) if there’s a deterministic algorithm that, on every input of size $n$, produces the correct yes/no answer within at most $p(n)$ steps for some fixed polynomial $p$ — $n^2$, $n^3$, $n \log n$, whatever, as long as it doesn’t depend on the particular input, only on its size. “Polynomial” is the dividing line the field has settled on between “efficient in principle” and “eventually intractable,” not because $n^{100}$ is fast in practice, but because polynomial-time algorithms compose cleanly (a polynomial number of polynomial-time subroutines is still polynomial-time) and, empirically, almost every problem that turns out to be in P at all turns out to have a polynomial algorithm with a small, usable exponent.

Some genuine, well-known members of P:

• Sorting. Comparison-based sorting algorithms (mergesort, heapsort) put $n$ numbers in order in $O(n \log n)$ time. Strictly speaking P is defined over yes/no questions, but the same notion of “polynomial time” extends naturally to search and function problems like this one — every function problem has a decision version (e.g. “is the $k$-th element of the sorted output equal to $v$?”) that inherits the same complexity, so the distinction rarely matters in practice.
• Shortest paths. Dijkstra’s algorithm finds shortest paths in a weighted graph in roughly $O(E \log V)$ time, so the decision question “is there a path from $s$ to $t$ of length at most $k$?” is answerable in polynomial time by just computing the real shortest path and comparing.
• Primality testing. For a long time, the fastest proven deterministic methods for testing whether a number is prime weren’t known to run in polynomial time (fast probabilistic tests existed, and prime witnesses gave an NP-style certificate, but an unconditional poly-time algorithm was open). That changed in 2002, when Agrawal, Kayal, and Saxena published the AKS primality test — a deterministic algorithm proving that PRIMES, “is $n$ prime?”, is in P, full stop.

P is the class of problems we can genuinely say we know how to solve efficiently, in the worst case, for every instance.

NP: easy to check, not (necessarily) easy to solve

NP is often introduced with a hand-wave — “solvable in polynomial time by a nondeterministic Turing machine” — and left there, as if that settled anything. It’s worth being precise, because there are actually two equivalent definitions, and the fact that they coincide is itself a small, satisfying theorem.

Definition 1 (verifier form). A decision problem $L$ is in NP if there is a polynomial-time algorithm $V$ (the verifier) and a polynomial $q$ such that: $x$ is a yes-instance of $L$ if and only if there exists some string $y$ (the certificate, or witness) with $|y| \le q(|x|)$ such that $V(x, y)$ accepts. In words: yes-instances have short proofs that a machine can check quickly. Nothing is said about how hard it is to find $y$ — only that once you have it, confirming it’s valid is fast.

Definition 2 (nondeterministic machine form). $L$ is in NP if there’s a nondeterministic Turing machine deciding it in polynomial time: at each step, the machine may branch into several possible next configurations at once (rather than one deterministic next step), and the input is accepted if at least one branch of the resulting computation tree leads to acceptance within a polynomial number of steps.

These sound different — one is about proof-checking, the other about a strange machine that can “try everything at once” — but they describe exactly the same class, and it’s worth seeing why. Given a verifier $V$, build a nondeterministic machine that, on input $x$, nondeterministically guesses a string $y$ of length up to $q(|x|)$ — meaning its branches collectively enumerate every possible string of that length — and then runs $V(x,y)$ deterministically along each branch. Some branch guesses the right certificate if one exists, and that branch accepts; the whole thing runs in polynomial time because guessing is “free” (it’s just branching) and the verification step is polynomial by assumption. That handles one direction. Going the other way: a polynomial-time nondeterministic machine has a bounded number of choices at each step (say $b$, fixed by its transition function) and runs for at most $p(|x|)$ steps, so a full accepting run can be recorded as a string describing which of the $b$ choices was taken at each of the $p(|x|)$ steps — a string of length $O(p(|x|) \log b)$, which is polynomial in $|x|$. That string is a certificate: a deterministic verifier can replay the machine’s transitions exactly as specified and check, in polynomial time, that this particular path really does end in acceptance. So a certificate is nothing more mysterious than a transcript of the “lucky guesses,” and checking it is just deterministic simulation.

Concrete NP problems, with their certificates:

• SAT. Given a Boolean formula, is there an assignment of true/false to its variables that makes it evaluate to true? Certificate: the assignment itself. Verification: plug it in, evaluate the formula, polynomial time.
• Subset-sum. Certificate: the subset. Verification: add up the numbers.
• Graph $k$-coloring. Given a graph, can its vertices be colored with $k$ colors so that no edge joins two same-colored vertices? Certificate: the coloring. Verification: check every edge, check every color used is in range.
• Hamiltonian path. Does a graph have a path visiting every vertex exactly once? Certificate: the sequence of vertices. Verification: check consecutive vertices are joined by an edge and nothing repeats.

Every problem in P is also in NP — trivially, since if you can solve it outright in polynomial time you don’t even need a certificate, or you can treat “the empty string” as the certificate and let the verifier just re-run the solver. So $P \subseteq NP$ is immediate; the open question is whether that containment is actually equality.

Reductions, and why some problems are “universally hard”

To compare the difficulty of different problems, complexity theory uses polynomial-time reductions. We say problem $A$ reduces to problem $B$ (written $A \le_p B$) if there’s a function $f$, computable in polynomial time, that transforms any instance $x$ of $A$ into an instance $f(x)$ of $B$, such that $x$ is a yes-instance of $A$ exactly when $f(x)$ is a yes-instance of $B$. The point of a reduction is that it transfers algorithms: if you had an efficient solver for $B$, you could solve $A$ efficiently too — just transform, then hand off to $B$‘s solver — because composing two polynomial-time procedures is still polynomial-time overall.

A problem $L$ is NP-complete if (1) $L$ is itself in NP, and (2) every problem in NP reduces to $L$ in polynomial time. Condition (2) is the striking part: it means an NP-complete problem is at least as hard as anything else in NP, in the specific sense that solving it efficiently would let you solve everything in NP efficiently, via the reduction. That makes the NP-complete problems into a kind of universal hard core of the class: they’re all polynomial-time equivalent to one another (each reduces to each of the others), so either all of them have polynomial-time algorithms, or none of them do. Crack one, and — through the whole web of reductions — you’ve cracked them all. Fail to crack one, and you’ve learned something about all of them at once.

The seed result here is the Cook–Levin theorem (Stephen Cook and, independently, Leonid Levin, 1971): Boolean satisfiability, SAT, is NP-complete. The proof works by directly encoding the run of an arbitrary polynomial-time nondeterministic Turing machine as a giant Boolean formula, built so that satisfying assignments correspond exactly to accepting computation histories — which is what makes SAT expressive enough to simulate any problem in NP. A year later, Richard Karp’s 1972 paper exhibited 21 further NP-complete problems — including graph coloring, the Hamiltonian cycle problem, subset-sum, clique, and vertex cover — each proven NP-complete by reducing SAT (or another already-known NP-complete problem) to it. That set off a chain reaction: once you have one NP-complete problem, proving a new one NP-complete just requires a single reduction from it, and today the catalogue runs into the hundreds, spanning graph theory, logic, scheduling, packing, and number theory.

Here’s roughly how these classes sit relative to one another, under the belief — not proof — that P and NP are actually different:

NP-hard is drawn as the wider circle because a problem can be “at least as hard as all of NP” (everything in NP reduces to it) without itself being in NP — it might not even be decidable at all. NP-complete is exactly the overlap: NP-hard problems that also happen to sit inside NP. P sits inside NP, off to the side of that overlap, under the conjecture that P-problems are strictly easier than the NP-complete ones. If it ever turned out that P = NP, this whole picture would collapse: P, NP, and NP-complete would all become the same set (restricted to problems inside NP).

The question itself, and why it resists an answer

Is P = NP? Spelled out: is it true that every decision problem whose yes-instances have short, quickly-checkable certificates also has an algorithm that finds such a certificate (or determines none exists) in polynomial time? Because of NP-completeness, this whole question boils down to a single instance of it: does SAT — or equivalently, any one NP-complete problem — have a polynomial-time algorithm? If yes, P = NP and the whole hierarchy above collapses. If SAT provably has no polynomial-time algorithm, then P ≠ NP.

What makes this deep rather than merely technical is the “for every problem, in the worst case” part. It isn’t asking whether checking and finding are usually comparably hard — in practice, industrial SAT solvers routinely handle formulas with millions of variables that arise from real chip-verification and planning problems. It’s asking whether there’s a genuine, unavoidable asymptotic gap between verifying and finding across the entire, enormously varied landscape of NP, or whether that gap is always just a polynomial-time illusion that a sufficiently clever algorithm could dissolve for every problem in the class simultaneously.

Most complexity theorists believe P ≠ NP. That belief rests on decades — over half a century now — of extremely capable people throwing combinatorial, algebraic, and algorithmic techniques at SAT and its relatives and never producing anything better than essentially exponential worst-case behavior (some exponents have been shaved down through cleverer branching and heuristics, but nothing polynomial has ever emerged). The sheer size and richness of the NP-complete family, all mutually reducible and none ever cracked, reads as strong circumstantial evidence. But that’s exactly what it is — circumstantial evidence, not a proof. It is entirely honest to say that nobody knows, and it would not be the first time a “surely true” mathematical belief turned out to be false.

Why is it so hard to prove P ≠ NP, given how much evidence points that way? Because a lower bound of this kind requires ruling out every possible polynomial-time algorithm, including ones nobody has thought of yet and ones that might use techniques totally unlike anything known today — it’s a claim about the limits of all possible cleverness, not just the cleverness that’s been tried. Contrast this with the halting problem, where undecidability is proven by a clean diagonalization argument: assume a halting-decider exists, build a machine that does the opposite of what it predicts about itself, derive a contradiction. It’s tempting to hope a similar trick could separate P from NP. It provably can’t, at least not on its own — this is the content of the relativization barrier (associated with Baker, Gill, and Solovay): there exist artificial “oracle” computational worlds in which P equals NP, and other oracle worlds in which P does not equal NP, and diagonalization-style arguments are exactly the kind of technique that works identically no matter what oracle you bolt on. A method that can’t tell these oracle worlds apart can’t be the thing that resolves P vs NP in our own, oracle-free world. A second, later obstruction known as the natural proofs barrier (associated with Razborov and Rudich) identified a broad class of combinatorial lower-bound techniques — ones that had successfully proven weaker circuit lower bounds — and showed that extending them to prove P ≠ NP outright would, as a side effect, break standard cryptographic hardness assumptions. Both of these are best understood as known obstructions ruling out entire families of proof strategies, not as evidence about which way the answer actually goes; they explain why the obvious hammers don’t work, not what the nail looks like.

Why this actually matters, beyond computer science

Cryptography. Nearly all of modern public-key cryptography — RSA, Diffie-Hellman key exchange, elliptic-curve cryptography — is built on exactly the checking-versus-finding asymmetry from the opening of this post. Multiplying two large primes is fast; recovering the primes from the product (factoring) is believed to be hard for classical computers, and nobody has ever published a classical polynomial-time factoring algorithm despite an obvious, enormous financial incentive to find one. The related discrete-logarithm problem underlies Diffie-Hellman and elliptic-curve schemes the same way. Factoring itself isn’t known to be NP-complete — it sits in NP ∩ coNP, which is actually a point of evidence against it being NP-complete — but it is unquestionably in NP: “does $N$ have a factor smaller than $k$?” has a certificate (the factor) that’s trivial to verify. Since every NP problem reduces to any NP-complete problem, a genuinely efficient, constructive algorithm for an NP-complete problem like SAT would give an efficient algorithm for the factoring decision problem too, by chaining the reduction to the SAT solver — and standard self-reducibility tricks turn a fast “yes/no, does a factor smaller than $k$ exist” oracle into the actual factors via repeated queries. So a practical proof that P = NP would, in a fairly direct chain of reasoning, threaten to unravel the hardness assumption that most of the internet’s encrypted traffic currently relies on.

The essential caveat, and it’s an important one: proving P = NP is not the same as handing the world a fast factoring algorithm tomorrow. A proof could in principle be non-constructive, or the algorithm it does yield could be a “galactic algorithm” — genuinely polynomial-time, but with such an enormous exponent or such astronomical hidden constants that it’s useless on any input smaller than the number of atoms in the observable universe. Complexity theory has real historical examples of galactic algorithms for other problems: theoretically dominant, practically inert. A resolution of P vs NP would be a monumental scientific event regardless of which way it went, but “P = NP” and “RSA breaks on my laptop next week” are not the same headline.

Optimization. Enormous classes of real-world problems — vehicle routing and logistics, airline crew and gate scheduling, exam and job-shop timetabling, chip layout, and the combinatorial search over candidate molecules in drug design — are NP-hard in their general, exact form. That’s why entire industries run on heuristics, integer-programming solvers, simulated annealing, and, increasingly, machine-learning-guided search, rather than exact optimal algorithms: the exact versions don’t scale, so practitioners settle for “good enough, fast enough” on the specific structured instances that actually arise. A genuinely practical algorithm for NP-hard optimization — again modulo the galactic-algorithm caveat — would mean provably optimal delivery routes, factory schedules, and molecular designs at a scale and certainty that’s simply unreachable today, which would be an economically transformative event across logistics, manufacturing, and pharmaceuticals simultaneously.

Creativity and discovery. Here’s the more speculative, and more fun, angle. A great deal of what feels like insight or creativity — finding a proof of a hard theorem, designing an elegant algorithm, composing something genuinely novel — has the same checking/finding shape: recognizing a good solution once it’s in front of you is often far easier than generating it from scratch. Given a candidate mathematical proof, verifying each inference step is mechanical; discovering the proof is the part we call genius. This gives rise to an appealing, informal slogan: if P = NP with a practical algorithm, then in some sense “if you can recognize genius, you can manufacture it” — automated theorem proving, and perhaps automated creative discovery more broadly, would become tractable in a way that currently looks out of reach. It’s worth being careful about this framing, though — it’s a heuristic intuition, not a theorem. Most of what we mean by mathematical creativity or artistic novelty isn’t cleanly formalizable as a decision problem with a fixed, bounded, polynomial-time-checkable certificate; theorems can have proofs of unbounded length, and “is this novel and interesting” isn’t a yes/no predicate with an obvious verifier. The slogan is a genuinely useful intuition pump for why P = NP would feel civilization-altering, not a rigorous corollary of it.

Where things stand

P vs NP is unproven in either direction. It is one of the seven Clay Mathematics Institute Millennium Prize Problems, each carrying a one-million-dollar prize for a correct resolution — the same set that includes the Riemann Hypothesis. Of the seven, only one has been resolved so far: the Poincaré conjecture, settled by Grigori Perelman in the early 2000s, who declined both the prize money and a Fields Medal for the work. P vs NP remains completely open. Most people in the field would bet on P ≠ NP if forced to bet, but it is exactly that — a bet, backed by circumstantial evidence and half a century of failed attacks in one direction, not a proof. It’s one of the rare places in mathematics where the “obvious” answer, the one nearly everyone believes, still has no proof at all, and there’s no guarantee one exists that we’re capable of finding.