# P vs NP, a primer

status: seedling · planted: 2026-10-03 · tended: 2026-10-03 · tags: programming, cognitive-science, math
url: https://latentmirror.com/posts/p-equals-np/

## What the question asks

[P vs NP](https://www.claymath.org/millennium/p-vs-np/) asks whether every problem whose answer is easy to check is also easy to find. Nobody knows, and the question has been open since Stephen Cook posed it in 1971 ([Cook, 1971](https://dl.acm.org/doi/10.1145/800157.805047)).

Sudoku is the easy way in. Checking a filled grid takes a minute: scan every row, column and box. Filling an empty grid can take far longer (and for bigger grids, it seems to explode).

The two letters name two kinds of problems:

**P:** problems a computer can *solve* in [polynomial time](https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time), i.e. the work grows like n² or n³ as the input grows (rather than like 2ⁿ).

**NP:** problems where a proposed answer can be *checked* in polynomial time ([NP](https://en.wikipedia.org/wiki/NP_(complexity))).

Every P problem is also an NP problem (if you can solve it fast, you can check it fast). The open question is whether the reverse holds. One caveat worth keeping in mind: "polynomial" is a theoretical stand-in for "fast". An algorithm that takes n¹⁰⁰ steps is technically polynomial and practically useless.



## Why it matters

The answer decides whether searching is fundamentally harder than recognizing. That reaches well past computer science.

**If P = NP** (with a practical algorithm): most [public-key cryptography](https://en.wikipedia.org/wiki/Public-key_cryptography) breaks; hard scheduling, routing and design problems become routine. The underrated part is mathematics itself. Finding a proof short enough to check would become about as easy as checking one.

**If P ≠ NP:** search stays hard, which is the world most experts believe we live in. (Cryptography actually needs more than P ≠ NP to be safe, so a proof would not settle that question on its own.)

The Clay Mathematics Institute offers $1 million for a proof either way; it is one of the seven [Millennium Prize Problems](https://www.claymath.org/millennium/p-vs-np/) named in 2000. In Bill Gasarch's 2019 poll of researchers, 88% expected P ≠ NP ([Gasarch, SIGACT News](https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf)).



## An amateur's intuition: choices that interact

My hunch from years of writing code: easy problems have choices that stay independent, and hard problems have choices that interact. It turns out the field has studied this from several angles.

Here is how I picture it. Any optimization problem is a set of unordered things that must be arranged to satisfy rules (positive or negative), with some quality score to maximize or minimize. An algorithm is a series of transformations of that set; each step costs some effort and nudges the quality up or down.

In sorting, moving one item into place does not change whether the other items meet the rules. Each fix stands alone. The [traveling salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) is the opposite: picking one road changes which roads make sense later. You can't know your future choices in advance without exploring the combinations.

The field captures this idea three ways:

**Greedy algorithms:** a classic theorem (Rado and Edmonds) pins down exactly when taking the locally best step, every time, is guaranteed to reach the global best. Those structures are called [matroids](https://en.wikipedia.org/wiki/Matroid). They are my "transformations that don't harm future choices", made precise.

**How much of the past you must remember:** this is the [dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming) view. The table below shows how that memory grows.

| Problem | What you must remember to continue correctly | Known status |
| --- | --- | --- |
| Sorting | Nothing | Easy (P) |
| Shortest path | Where you are now | Easy (P) |
| Traveling salesman | Which cities you've already visited (2ⁿ possibilities) | Hard (NP-hard) |

That last row is why the best exact salesman algorithm ([Held and Karp, 1962](https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm)) still takes exponential time.

**Frustration:** physicists use this word for constraints that can't all be satisfied at once ([geometrical frustration](https://en.wikipedia.org/wiki/Geometrical_frustration)). It makes the "energy landscape" rugged: full of dead ends where every small change looks worse, yet you are not at the best answer. Sorting has no such dead ends. Each swap of an out-of-order neighbouring pair fixes exactly one problem. Finding the lowest-energy state of a 3D [spin glass](https://en.wikipedia.org/wiki/Spin_glass) (a frustrated magnet) is NP-hard ([Barahona, 1982](https://doi.org/10.1088/0305-4470/15/10/028)).

## Where the intuition breaks

Interacting choices don't, on their own, make a problem hard. Some of the most tangled problems turn out to be easy.

**2-SAT:** every choice forces other choices through a chain of implications. Still, [2-SAT](https://en.wikipedia.org/wiki/2-satisfiability) can be solved in linear time. Its close cousin [3-SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem) is NP-complete.

**Matching:** pairing people or tasks so as many as possible are matched is full of interacting choices. But Jack Edmonds found a polynomial algorithm in 1965, in the same paper that proposed polynomial time as the definition of an "efficient" algorithm ([Edmonds, 1965](https://doi.org/10.4153/CJM-1965-045-4)).

**Linear programming:** every variable interacts with every other, yet [linear programming](https://en.wikipedia.org/wiki/Linear_programming) is solvable in polynomial time. Its landscape has no false peaks (any local best is the global best). Even so, the classic method that climbs it can take exponential time ([Klee–Minty](https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube)); the first polynomial algorithm, the [ellipsoid method](https://en.wikipedia.org/wiki/Ellipsoid_method), came in 1979.

In each case, a clever change of viewpoint made the interaction stop mattering. That is the real gap. Proving P ≠ NP means showing no such viewpoint exists for any NP-complete problem, against every possible algorithm (including ones nobody has imagined yet).

So my intuition is a decent guide to which problems *feel* hard. It can't be the proof.

## Why a proof is so hard

Three proven "barrier" results rule out most of the proof techniques we know. Any serious attempt has to explain how it gets around all three.

| Barrier | Who and when | What it rules out |
| --- | --- | --- |
| Relativization | [Baker, Gill and Solovay, 1975](https://doi.org/10.1137/0204037) | Arguments that still work when every machine gets the same magic helper (an "oracle"); this includes [diagonalization](https://en.wikipedia.org/wiki/Diagonal_argument), the trick behind the [halting problem](https://en.wikipedia.org/wiki/Halting_problem) |
| Natural proofs | [Razborov and Rudich, 1994](https://doi.org/10.1006/jcss.1997.1494) | Most circuit lower-bound arguments; one strong enough to separate P from NP would also break cryptography we believe is secure |
| Algebrization | [Aaronson and Wigderson, 2008](https://www.scottaaronson.com/papers/alg.pdf) | Turning logic into polynomials (the trick that cracked other big results) is not enough on its own either |

The [natural proofs](https://en.wikipedia.org/wiki/Natural_proof) barrier is my favourite: believing that hard problems exist is exactly what stops you from proving that hard problems exist.

The live research programs ([geometric complexity theory](https://en.wikipedia.org/wiki/Geometric_complexity_theory), [proof complexity](https://en.wikipedia.org/wiki/Proof_complexity), [meta-complexity](https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/)) are all attempts to find a path around these walls. Lance Fortnow, who has tracked the problem for decades, wrote in June 2026 that there is not yet even a viable approach ([Computational Complexity blog](https://blog.computationalcomplexity.org/2026/06/respect-p-v-np-problem.html)).



## The "verified proof" mirage

A Lean proof guarantees every step follows from the last. It does not guarantee the theorem means what its title says.

[Lean](https://lean-lang.org/) is a proof assistant: a small trusted program (the kernel) checks each step of a proof. [Lean's own documentation](https://lean-lang.org/doc/reference/latest/ValidatingProofs/) separates two questions: did Lean accept a proof of the formal statement, and does that statement actually mean what the author claims? Only the first is automatic.



There are three common ways a "verified" proof goes wrong:

**Definitions:** P and NP get defined as something simpler (or meaningless) that is easier to prove things about.

**Premises:** the hard part sits as an assumption inside the theorem's own statement. Lean's `#print axioms` report does not flag these.

**Axioms:** big cited results are assumed rather than proved.

The June 2026 paper claiming a Lean-verified proof that P = NP ([arXiv 2606.03194](https://arxiv.org/abs/2606.03194)) is a live example. According to a [PostQuantum report](https://postquantum.com/industry-news/aix-global-innovations-millennium-prize/), a [GitHub issue](https://github.com/TiruArt/Pedigree-Polytopes-Lean4/issues/1) opened the next day showed its top-level proposition was first defined as `True`. It was later revised to an axiom never formally connected to real complexity classes. Meanwhile, a [separate Lean package](https://reservoir.lean-lang.org/@Mintpath/p_ne_np/dependencies) claims a machine-verified proof that P ≠ NP. Both can't be right.

In September, a company called AIX Global claimed to have solved all six remaining Millennium Prize Problems. Its own audit script marked the P ≠ NP result as conditional on unproven premises ([same report](https://postquantum.com/industry-news/aix-global-innovations-millennium-prize/)).

The Clay Institute guards against all of this by design. It [accepts no direct submissions](https://www.claymath.org/millennium-problems/rules/); a solution must be published in a qualifying outlet, survive two years of scrutiny, and win general acceptance.

## Sudoku: the whole primer in one puzzle

Sudoku holds every idea above in miniature: easy to check, hard to fill, and full of interacting choices.

**Check vs. find:** verifying a finished grid is quick; finding the answer from scratch can mean a lot of trial and error.

**Interacting choices:** every digit you place constrains its row, its column and its box. That is my sorting-vs-salesman intuition at kitchen-table scale.

**Where hardness actually lives:** Yato and Seta proved in 2003 that Sudoku generalized to any size (n² × n² grids) is NP-complete ([mathematics of Sudoku](https://en.wikipedia.org/wiki/Mathematics_of_Sudoku)). The ordinary 9 × 9 grid is a fixed size, so a computer solves it in an instant. Complexity is about how the work *grows*, which is easy to forget.

**Propagation vs. search:** most newspaper puzzles fall to pure deduction ([constraint propagation](https://en.wikipedia.org/wiki/Constraint_propagation): each placement forces the next). The hardest ones need guessing and [backtracking](https://en.wikipedia.org/wiki/Backtracking). That split mirrors 2-SAT and 3-SAT: when forced moves run out, you are left searching.

To watch that search happen, [Sudoku Search Lab](/artifacts/sudoku-search-lab/) shades every cell by how often the solver touched it and counts the backtracks.

## Further reading

- Lance Fortnow, [*The Golden Ticket*](https://press.princeton.edu/books/paperback/9780691175782/the-golden-ticket) (book-length popular treatment)
- Michael Sipser, [*Introduction to the Theory of Computation*](https://en.wikipedia.org/wiki/Introduction_to_the_Theory_of_Computation), chapters 7 to 9 (the standard on-ramp)
- Scott Aaronson, ["Why Philosophers Should Care About Computational Complexity"](https://www.scottaaronson.com/papers/philos.pdf) (essay)
- Scott Aaronson, ["P =? NP"](https://www.scottaaronson.com/papers/pnp.pdf) (the best single map of the field)
- Avi Wigderson, [*Mathematics and Computation*](https://www.math.ias.edu/avi/book) (free online)
- Gerhard Woeginger's [P-versus-NP page](https://wscor.win.tue.nl/woeginger/P-versus-NP.htm) (a catalogue of claimed proofs, all wrong)

Sources:

- [Respect the P v NP Problem](https://blog.computationalcomplexity.org/2026/06/respect-p-v-np-problem.html) (Fortnow, June 2026)
- [AIX's Millennium Problem Claims Fail Their Own Audit](https://postquantum.com/industry-news/aix-global-innovations-millennium-prize/) (PostQuantum, September 2026)
- [Lean 4 Verified P=NP via Pedigree Polytope](https://www.emergentmind.com/papers/2606.03194) (paper summary)
- [Fifty Years of P vs. NP](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/) (Fortnow, CACM)

## Connections

**Related:** [Twenty-eight choices](https://latentmirror.com/posts/twenty-eight-choices/), [Recursive Self-Improvement — the RSI Ladder and the Verification Problem](https://latentmirror.com/reflections/recursive-self-improvement-cluster/)