# P vs NP: Checking Is Easy, Finding Is Hard

> On 26 October 2026 OpenAI said one of its models had disproved the Exponential Time Hypothesis, a widely believed assumption about how hard certain logic puzzles are; hours later Anthropic posted a refutation of its own, and leading computer scientists began an open check of both claims. This film explains the fundamentals underneath: why checking an answer can be far easier than finding one; polynomial versus exponential time; the classes P and NP; Gödel’s 1956 letter; how Cook, Levin and Karp showed that thousands of problems, from Sudoku to route planning, rise or fall together; why modern encryption depends on hardness; the million-dollar Clay prize; and what the new claim would, and would not, change.

Interactive film: https://www.planetpast.com/stories/p-vs-np-problem/  
Publisher: PlanetPast (https://www.planetpast.com/) · d => T('readPublished', l, { d: dateIn(d, l) }) 2026-10-28 · Math, Technology

## Prologue

### Checking is easy, finding is hard
*Mathematics · Technology*

Or is it? A million-dollar question.

On the twenty-sixth of October 2026, OpenAI said one of its AI models had overturned a widely believed assumption about how hard certain logic puzzles are. Hours later, Anthropic said its own model had done the same. Hundreds of research papers rest on that assumption. So leading computer scientists are now checking both claims in the open, and nobody has confirmed them yet. To see why this matters, start with a simple puzzle, and a question worth a million dollars.

- **ETH**: the Exponential Time Hypothesis, proposed in 1999
- **Hundreds**: of computer-science papers rely on it (TNW)

> “Our involvement should not be taken as certification of the claim.” (Open letter of the examining computer scientists, via The Next Web)

- Why checking beats finding
- Fast and slow algorithms
- P, NP and NP-complete
- What the new claim would change

Prologue

#### A claim under examination

The Next Web (26 Oct 2026): OpenAI announced that an internal model had refuted the Exponential Time Hypothesis, which OpenAI itself describes as “widely believed to be true”; it says the model found the disproof on 16 October, that it was checked in the Lean proof assistant on 17 October, and that the write-up and Lean proof are on GitHub. Russell Impagliazzo and Ramamohan Paturi (UC San Diego) and Ryan Williams (MIT) are leading an open, independent examination; their letter says “Our involvement should not be taken as certification of the claim” and “If the claim is correct, it will change an important part of theoretical computer science.” TechCrunch (27 Oct 2026): hours after an Anthropic mathematician suggested OpenAI’s work drew on earlier results, Anthropic released its own refutation on GitHub.

The 2026 claims are unverified at the time of this film: independent experts are still examining them.

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [The Next Web (26 Oct 2026): OpenAI says its AI model has disproved the Exponential Time Hypothesis (dates, Lean check, the open examination)](https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/)

## Chapter I · Checking versus finding

### Checking versus finding
*Chapter I*

One is quick. The other may not be.

Here is a finished Sudoku. To check it, you only look along each row, each column and each box for a repeated number. It takes a minute. Finding the answer from a nearly empty grid is another matter. You try a number, back up, and try again, and on bigger and bigger grids the possibilities explode. Checking is easy. Finding seems hard. This whole film is about whether that difference is real.

- 9 rows: no repeats
- 9 columns: no repeats
- 9 boxes: no repeats
- Press “Check” in the scene

![A pencil over a puzzle grid. For the general n² × n² Sudoku, finding a solution is NP-complete (Fortnow, 2009). AI-generated illustration.](https://assets.planetpast.com/a/88/881817b7bc8339ca.jpg)

- **Check**: one pass over the grid
- **Find**: possibly a search through countless options

Chapter I · Checking versus finding

#### Easy to check

Lance Fortnow, Communications of the ACM (2009): solving an n² × n² Sudoku puzzle is NP-complete, along with problems such as clique, 3-colouring and Hamiltonian cycle; checking a proposed solution needs only one pass through the rows, columns and boxes. TechCrunch (27 Oct 2026) uses the same example: Sudoku solutions are easy to check but hard to find.

Try it: check the grid, then break it by swapping two cells and check again. A standard 9 × 9 Sudoku is small enough for computers to solve quickly; the hardness is about how the work grows as grids get bigger.

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/)

### 

The Clay Mathematics Institute gives another example. Is 13,717,421 the product of two smaller numbers? Finding them by hand could take a very long time. But if someone tells you the answer, 3,607 times 3,803, you can check it with a calculator in seconds. Many practical problems share this shape: a good answer may be hard to find, but quick to recognise once you see it.

![An old mechanical calculator. Trying divisors one by one, you would reach 3,607 only after hundreds of tries among the primes alone. AI-generated illustration.](https://assets.planetpast.com/a/3b/3b8aee305699a2af.jpg)

$$3607 \times 3803 = 13\,717\,421$$
- $3607,\ 3803$: the two factors: hard to find, easy to check

- A delivery route under a distance limit
- A timetable with no clashes
- Packing boxes to a weight limit

Chapter I · Checking versus finding

#### Hard to find, easy to check

Clay Mathematics Institute (problem description): finding two numbers whose product is 13,717,421 is hard, but anyone can check with a calculator that 3,607 × 3,803 = 13,717,421. The institute also gives a party example: checking a claim that you know someone at the party is quick, while finding them yourself may mean checking every guest.

Try it: multiply the two factors, then try to factor the number by trial division and watch the counter. The routing, timetable and packing examples are versions of the travelling salesman, scheduling and knapsack problems, all in NP (Britannica; Karp, 1972).

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [Clay Mathematics Institute problem description of P vs NP (mirror): the party and factoring examples](https://www.mi.sanu.ac.rs/~zorano/izazovi21vek/p_vs_np.html); [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [Wikipedia: Karp’s 21 NP-complete problems](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems)

## Chapter II · Fast and slow

### Fast and slow
*Chapter II*

How the work grows decides everything.

Computer scientists judge an algorithm by how its running time grows as the problem gets bigger. If the input has n parts, a fast method might take about n squared steps. In 1965 Jack Edmonds proposed what counts as a good algorithm: one whose number of steps is bounded by a fixed polynomial in the size of the input, like n squared or n cubed. An exponential method is different. Its steps grow like two to the power n: every extra part doubles the work. At n equals ten, n squared is a hundred and two to the n is about a thousand. At a hundred, n squared is ten thousand, while two to the n is a number with thirty-one digits.

$$n^2 \quad \text{(polynomial)}$$
$$2^n \quad \text{(exponential)}$$
- $n$: size of the input

- **“Paths, trees, and flowers”**: the paper, with a fast algorithm for matching pairs

- **2¹⁰ = 1,024**: n = 10
- **2¹¹ = 2,048**: n = 11
- **2¹² = 4,096**: n = 12

- n²: 10,000
- n³: 1,000,000
- 2ⁿ: ≈ 1.27 × 10³⁰

Chapter II · Fast and slow

#### Polynomial and exponential

Britannica: P is the class of problems whose number of steps is bounded by a polynomial in the input length n; these are treated as easy, or tractable. Fortnow (2009) and Sipser (1992): in “Paths, trees, and flowers” (1965) Jack Edmonds gave a polynomial-time algorithm for matching and proposed that efficient computation means time bounded by a fixed polynomial in the input size, the idea that later became the class P.

The numbers are arithmetic: 10² = 100, 2¹⁰ = 1,024, 100² = 10,000, and 2¹⁰⁰ ≈ 1.27 × 10³⁰, which has 31 digits. Try it: change n and compare the bars. The bars are drawn on a logarithmic scale (their height is the number of digits), otherwise 2ⁿ would leave the screen.

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf); [Michael Sipser (1992): The history and status of the P versus NP question (Gödel’s 1956 letter, Edmonds)](https://www.cs.columbia.edu/~tal/3261/sipserpnp.pdf)

### 

Here is the kind of puzzle at the centre of the news. A logic formula has n switches, each true or false, and a list of rules about them. Is there a setting of the switches that obeys every rule? This is called the satisfiability problem, or SAT. Checking a proposed setting is quick: go through the rules one by one. But the obvious way to find one is to try every setting, and n switches have two to the n settings. Add ten switches, and there are about a thousand times more to try.

- n switches: true or false
- Rules such as “A or not B or C”
- Goal: every rule satisfied at once

![A panel of old toggle switches. With 30 switches there are already about 1.07 billion settings. AI-generated illustration.](https://assets.planetpast.com/a/7e/7e411a1c1ccc1093.jpg)

- **1,024**: n = 10
- **≈ 1.07 billion**: n = 30
- **≈ 1.27 × 10³⁰**: n = 100

$$2^{n+10} = 1024 \times 2^{n}$$
- $+10$: ten more switches

Chapter II · Fast and slow

#### The satisfiability problem

Impagliazzo & Paturi: k-SAT asks whether a formula in k-CNF form (an AND of rules, each an OR of k switches or their negations) has a satisfying assignment. Brute force tries all 2ⁿ assignments of n variables. Britannica: checking a proposed solution of an NP problem takes polynomial time.

Try it: flip the switches at random, or run the brute-force search and watch the counter against 2ⁿ. The scene uses 12 switches (4,096 settings). Cleverer algorithms beat plain brute force, but every algorithm known before the October 2026 claims still took exponential time (Institute for Advanced Study).

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [Impagliazzo & Paturi: Complexity of k-SAT (the Exponential Time Hypothesis), UC San Diego](https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_1999_ccc.pdf); [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [Institute for Advanced Study: Do NP-hard problems require exponential time?](https://ias.edu/node/74266)

## Chapter III · The question

### The question
*Chapter III*

Is every quick check also a quick find?

Now the two families. P is the set of problems that can be solved in polynomial time: the ones we count as tractable. NP is the set of problems where a proposed answer can be verified in polynomial time. Sudoku, SAT and the factoring puzzle are all in NP. Every problem in P is also in NP: if you can find an answer quickly, you can certainly check one quickly. The open question is the other direction. If every quickly checkable problem can also be solved quickly, then P equals NP. Most researchers think not. Nobody has proved it either way.

- Solvable in polynomial time
- Example: sorting a list
- Example: finding the shortest road route

- Answers checkable in polynomial time
- Includes all of P
- Includes SAT, Sudoku, factoring
- NP stands for “nondeterministic polynomial time”, not “not polynomial”

$$\mathrm{P} \subseteq \mathrm{NP}$$
$$\mathrm{P} \overset{?}{=} \mathrm{NP}$$
- $\subseteq$: “is contained in”

- **Open**: no proof either way
- **$1 million**: Clay prize for a correct proof

Chapter III · The question

#### P and NP

Britannica: P contains the problems whose number of steps is bounded by a polynomial in n; NP contains the problems for which a guessed solution can be verified in polynomial time. P is a subset of NP. The question is whether P equals NP, that is, whether every problem whose solution can be verified quickly can also be solved quickly. TechCrunch: most researchers assume P ≠ NP.

Sorting and shortest paths are standard textbook examples of problems with polynomial-time algorithms. The rings in the scene show the classes as most researchers believe them to be; if P = NP the inner ring would fill the outer one.

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/)

### 

The question is older than most computers. In 1956 the logician Kurt Gödel wrote about it to the dying John von Neumann. He asked how fast a machine’s work would grow if it had to decide whether a statement has a proof of a given length. If it grew slowly, he wrote, the mental effort of mathematicians on yes-or-no questions could be replaced by machines, with consequences of the greatest magnitude.

![A 1950s letter and fountain pen. The original of Gödel’s letter is held in the Library of Congress (Sipser). AI-generated illustration.](https://assets.planetpast.com/a/2d/2de607e037658300.jpg)

> “…consequences of the greatest magnitude.” (Kurt Gödel to John von Neumann, 1956 (translation in Sipser, 1992))

- 1955: John Nash conjectures code-breaking time grows exponentially with key length
- 1956: Gödel’s letter
- 1965: Edmonds: efficient = polynomial

Chapter III · The question

#### Gödel’s lost letter

Sipser (1992): in 1956 Gödel wrote to von Neumann, who was dying, asking how fast the number of steps grows for a machine that decides whether a formula has a proof of length n, growing like Kn or Kn²? If so, he wrote, the mental effort of the mathematician in the case of yes-or-no questions could be completely replaced by machines, with “consequences of the greatest magnitude”. The original letter is in the Library of Congress. Wikipedia: in 1955 John Nash wrote to the US National Security Agency speculating that the time to break a code would grow exponentially with the key length, while doubting it could be proved.

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [Michael Sipser (1992): The history and status of the P versus NP question (Gödel’s 1956 letter, Edmonds)](https://www.cs.columbia.edu/~tal/3261/sipserpnp.pdf); [Wikipedia: P versus NP problem (consequences)](https://en.wikipedia.org/wiki/P_versus_NP_problem)

## Chapter IV · All or nothing

### All or nothing
*Chapter IV*

Many problems, one fate.

In 1971 Stephen Cook proved something remarkable. Every problem in NP can be quickly translated into SAT, the switch puzzle. So a fast way to solve SAT would give a fast way to solve every problem in NP. Problems with this property are called NP-complete, and SAT was the first. Leonid Levin found the same idea independently and published it in 1973. Cook later received the Turing Award, often called the Nobel prize of computing, for this work.

- **1971**: Cook, at the ACM STOC conference
- **1973**: Levin, independently

- It is in NP
- Every NP problem translates into it quickly
- Solve it fast, solve all of NP fast

![A plain trophy on a desk of papers. Cook received the Turing Award in 1982. AI-generated illustration.](https://assets.planetpast.com/a/98/989033725b0aeb92.jpg)

Chapter IV · All or nothing

#### The first NP-complete problem

ACM: Stephen Cook’s paper “The complexity of theorem-proving procedures”, presented at the 3rd ACM Symposium on Theory of Computing (STOC) in 1971, showed that SAT is NP-complete, the first such problem; Leonid Levin independently found the same ideas (published 1973); Cook received the Turing Award in 1982. Britannica: an NP-complete problem is in NP and at least as hard as every other problem in NP, so an efficient algorithm for any one of them would give efficient algorithms for all problems in NP.

Try it: press “Solve SAT fast” and watch the solution flow along the translations to every problem linked to it. The network is a diagram, not a full map of known reductions.

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [ACM A.M. Turing Award: Stephen A. Cook (1982)](https://amturing.acm.org/award_winners/cook_n991950.cfm); [Encyclopaedia Britannica: NP-complete problem](https://britannica.com/science/NP-complete-problem); [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem)

### 

A year later Richard Karp showed that twenty-one well-known problems are NP-complete too, including colouring a network, finding a round trip that visits every point exactly once, and packing a knapsack. Many more have joined the list since, among them the travelling salesman problem and large Sudoku grids. They stand or fall together. Find a fast method for any one of them, and you have one for all of them, and P equals NP. Prove that any one of them has no fast method, and P does not equal NP. Try colouring this network with three colours, so that no two linked points match. Checking is instant. Finding can take a while.

- Chromatic number (graph colouring)
- Hamiltonian circuit
- Knapsack
- Clique, 3-SAT and more

![Pins and thread on an old map, tracing a tour. Checking that a given tour is under a distance limit is quick. AI-generated illustration.](https://assets.planetpast.com/a/97/97d19d2d6eb1ae69.jpg)

- **Any one fast**: → all fast: P = NP
- **One proved slow**: → P ≠ NP

- **19**: points
- **3**: colours allowed
- **3¹⁹**: possible colourings: about 1.16 billion

Chapter IV · All or nothing

#### Twenty-one problems, then many more

Richard Karp, “Reducibility Among Combinatorial Problems” (1972), showed 21 problems NP-complete, including SAT, 3-SAT, chromatic number (graph colouring), clique, Hamiltonian circuit and knapsack (ACM; Wikipedia). Britannica lists the travelling salesman problem and SAT as NP-complete; Fortnow (2009) adds 3-colouring and n² × n² Sudoku. Britannica: an efficient algorithm for any NP-complete problem would give efficient algorithms for all problems in NP.

Try it: colour the network at random and check (clashes turn red), or let the computer search: it tries colours one point at a time and backs up when stuck. This small network is quick; the difficulty is how the search grows with size.

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [ACM A.M. Turing Award: Stephen A. Cook (1982)](https://amturing.acm.org/award_winners/cook_n991950.cfm); [Wikipedia: Karp’s 21 NP-complete problems](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems); [Encyclopaedia Britannica: NP-complete problem](https://britannica.com/science/NP-complete-problem); [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf)

## Chapter V · Why it matters

### Why it matters
*Chapter V*

A prize, and the locks on the internet.

In 2000 the Clay Mathematics Institute named P versus NP one of seven Millennium Prize Problems, with a million dollars for a solution. Only one of the seven, the Poincaré conjecture, has been solved. The stakes are practical too. Much of modern encryption rests on the belief that some problems, like factoring the product of two large primes, cannot be solved quickly. Factoring is in NP, but it is not believed to be NP-complete, so even a proof that P does not equal NP would not prove that factoring is hard. The other direction is clearer. As the computer scientist Lance Fortnow puts it, if P equals NP, public-key cryptography is impossible.

- **7**: problems, announced 24 May 2000 in Paris
- **$1 million**: for each
- **1**: solved so far: Poincaré

![A padlock on a server rack. Britannica: modern cryptography relies on the assumption that factoring is not in P. AI-generated illustration.](https://assets.planetpast.com/a/f2/f21e9c5af24aa559.jpg)

- In NP: an answer is easy to check
- Not believed to be NP-complete
- Its hardness is assumed, not proved

> “If P = NP then public-key cryptography is impossible.” (Lance Fortnow, Communications of the ACM, 2009)

Chapter V · Why it matters

#### A prize and a lock

Clay Mathematics Institute: the Millennium Prize Problems were announced on 24 May 2000 at the Collège de France in Paris, with $1 million for each of seven problems; the Poincaré conjecture is the only one solved. Britannica: modern cryptography assumes that factoring a product of two large primes is not in P, and an efficient factoring method would break most modern encryption. Fortnow (2009): “If P = NP then public-key cryptography is impossible”; factoring and discrete logarithms are not expected to be NP-complete.

The 3D lock is a metaphor: two primes multiply easily into one number, which is hard to split again.

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [Clay Mathematics Institute: The Millennium Prize Problems](https://www.claymath.org/millennium-problems); [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf)

### 

If P did equal NP, and the method were practical, many hard planning problems would become easy, and computers could search for proofs of theorems, as Cook himself pointed out. Most experts doubt it. In William Gasarch’s 2019 poll of 124 researchers, eighty-eight percent believed that P does not equal NP, and twelve percent that it does. But a poll is not a proof, and this month’s claims show that even widely held beliefs get tested. Try both worlds.

- Route and logistics problems become efficiently solvable
- Reasonable-length proofs could be found by computer
- Many design and scheduling searches would become quick

- 2002: 61%
- 2012: 83%
- 2019: 88%

- P ≠ NP: the inner ring stays small
- P = NP: the inner ring fills NP
- Nobody knows which world we live in

Chapter V · Why it matters

#### What if?

Wikipedia, summarising the literature: if P = NP, many logistics problems such as the travelling salesman would become efficiently solvable, and computers could find formal proofs of theorems that have proofs of reasonable length, a possibility Cook described; public-key cryptography would be at risk. Gasarch’s polls of researchers: 61% believed P ≠ NP in 2002 (100 respondents), 83% in 2012 (152) and 88% in 2019 (124, conducted in 2018); 9%, 9% and 12% believed P = NP.

A proof that P = NP might give an algorithm that is polynomial but far too slow to use; the consequences above assume a practical one. Try it: switch between the two worlds.

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [Wikipedia: P versus NP problem (consequences)](https://en.wikipedia.org/wiki/P_versus_NP_problem); [William Gasarch (2019): The third P =? NP poll](https://www.cs.umd.edu/users/gasarch/papers/poll3.pdf); [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf)

## Chapter VI · The new claim

### The new claim
*Chapter VI*

A stronger bet, and the machines that challenge it.

The Exponential Time Hypothesis goes further than P versus NP. Russell Impagliazzo and Ramamohan Paturi set it out in 1999: three-SAT, the switch puzzle with three switches per rule, cannot be solved in sub-exponential time. In other words, every method needs time that grows at least like two to the power of some fixed fraction of n, still doubling at a steady rate. A sub-exponential method would grow more slowly than any of those, though not necessarily as slowly as a polynomial. It is a stronger bet than P not equal to NP: if it is true, then P does not equal NP. Press the buttons to compare the curves. Hundreds of computer-science papers rest on it, using it to show how fast other problems can, and cannot, be solved.

$$\exists\, \delta > 0:\ \text{3-SAT needs } 2^{\delta n} \text{ time}$$
- $\delta$: some fixed positive fraction
- $n$: number of switches (variables)

$$2^{n},\ 2^{n/10} \quad \text{exponential}$$
$$2^{\sqrt{n}} \quad \text{sub-exponential}$$
$$n^{3} \quad \text{polynomial}$$
- $2^{\sqrt{n}}$: a textbook example, not the claimed algorithm

- ETH true → P ≠ NP true
- ETH false → P vs NP still open
- ETH is “a strengthening of P ≠ NP” (MIT notes)

- **Hundreds**: of computer-science papers
- **1999**: first published by Impagliazzo and Paturi

Chapter VI · The new claim

#### The Exponential Time Hypothesis

Impagliazzo & Paturi: let s_k be the smallest δ such that k-SAT has an O(2^{δn}) algorithm; the Exponential Time Hypothesis states that s_k > 0 for k ≥ 3, “in other words, for k ≥ 3, k-SAT does not have a subexponential-time algorithm.” TechCrunch: Impagliazzo and Paturi first published ETH in 1999. MIT lecture notes (V. Vassilevska Williams): ETH says there is a δ > 0 such that 3-SAT requires 2^{δn} time, “a strengthening of P ≠ NP”. The Next Web: hundreds of computer-science papers rest on ETH.

The orange band in the scene is the family of curves 2^{δn}; ETH says 3-SAT stays above one of them. Shapes are illustrative.

The switches, grids, maps and diagrams are teaching models. Step counts in the scenes are illustrations of growth, not timings of real computers.

Sources: [Impagliazzo & Paturi: Complexity of k-SAT (the Exponential Time Hypothesis), UC San Diego](https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_1999_ccc.pdf); [MIT 6.S078 lecture notes (V. Vassilevska Williams): ETH as a strengthening of P ≠ NP](https://people.csail.mit.edu/virgi/6.s078/lect2.pdf); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/); [The Next Web (26 Oct 2026): OpenAI says its AI model has disproved the Exponential Time Hypothesis (dates, Lean check, the open examination)](https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills)

### 

OpenAI says its model found the disproof on the sixteenth of October, and that it was checked the next day in Lean, a program that verifies proofs line by line. The labs claim algorithms that solve these puzzles in sub-exponential time. Impagliazzo, Paturi and Ryan Williams of MIT are leading the open examination. Williams says parts of the proof look routine, but a few look unusual enough to need the whole community’s effort. OpenAI says it is reasonably confident the result does not break cryptography. And even if it holds, a sub-exponential method is not a polynomial one, so it would not by itself show that P equals NP. Williams says it should give that possibility a little more weight, but he doubts this algorithm is the best possible.

- Sub-exponential algorithms for these SAT puzzles
- Proof checked in Lean, posted on GitHub
- Not yet independently confirmed

![Printed pages and notes spread on a seminar table. The examiners asked OpenAI to release all raw data and fund a conference; it agreed (TNW). AI-generated illustration.](https://assets.planetpast.com/a/92/92844c4e4483e747.jpg)

- ETH is false
- Papers that assumed ETH need revisiting
- P vs NP is still open

- **OpenAI**: announced 26 Oct; proof on GitHub
- **Anthropic**: own refutation on GitHub, per TechCrunch

Chapter VI · The new claim

#### Under examination

The Next Web: OpenAI says the model found the disproof on 16 October and it was checked in Lean on 17 October; the examining scientists signed no NDAs and are unpaid, and asked OpenAI to release all raw data and fund a conference, which it agreed to. TechCrunch: both labs claim algorithms that solve these hard logic puzzles in sub-exponential time; Williams said some parts look routine but “two or three” look alien and warrant community effort; he said scientists should give somewhat more weight to P = NP, doubts OpenAI’s algorithm is the best possible, and asked whether it breaks cryptography, to which OpenAI said it was “reasonably confident” it does not. Many papers that rely on ETH may need revisiting if the claims hold.

Refuting ETH shows only that 3-SAT has a sub-exponential algorithm; a sub-exponential algorithm need not be polynomial, so P vs NP is not settled by it. Anthropic’s refutation is reported by TechCrunch; this film found no Anthropic statement to cite directly.

The 2026 claims are unverified at the time of this film: independent experts are still examining them.

Sources: [The Next Web (26 Oct 2026): OpenAI says its AI model has disproved the Exponential Time Hypothesis (dates, Lean check, the open examination)](https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/)

## Epilogue

### 

Checking is easy; finding seems hard. For seventy years nobody has proved whether that gap is a law of nature, or a missing idea. This month, machines joined the search. Whether their proofs survive is now being decided the way the question itself predicts: checking, the easy part, one careful step at a time.

- 1956: Gödel’s letter
- 1965: Edmonds: efficient = polynomial
- 1971: Cook: SAT is NP-complete
- 1972: Karp’s 21 problems
- 2000: Clay’s $1 million prize
- 2026: AI claims against ETH, under review

![Gödel asked his question in 1956; the Clay prize for answering it has stood unclaimed since 2000. AI-generated illustration.](https://assets.planetpast.com/a/2d/2de607e037658300.jpg)

- Stills and pictures are AI-generated
- Scenes are teaching models
- The 2026 claims are unverified

Epilogue · Sources

#### Sources

Every fact in this film comes from the sources below. The chapter stills and pictures are AI-generated illustrations; the scenes are teaching models. The October 2026 claims are reported as claims: at the time of this film, independent experts were still examining them, and their outcome may change what is said in the last chapter.

Sources: [The Next Web (26 Oct 2026): OpenAI says its AI model has disproved the Exponential Time Hypothesis (dates, Lean check, the open examination)](https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/); [Impagliazzo & Paturi: Complexity of k-SAT (the Exponential Time Hypothesis), UC San Diego](https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_1999_ccc.pdf); [MIT 6.S078 lecture notes (V. Vassilevska Williams): ETH as a strengthening of P ≠ NP](https://people.csail.mit.edu/virgi/6.s078/lect2.pdf); [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [Encyclopaedia Britannica: NP-complete problem](https://britannica.com/science/NP-complete-problem); [Clay Mathematics Institute: The Millennium Prize Problems](https://www.claymath.org/millennium-problems); [Clay Mathematics Institute problem description of P vs NP (mirror): the party and factoring examples](https://www.mi.sanu.ac.rs/~zorano/izazovi21vek/p_vs_np.html); [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf); [Michael Sipser (1992): The history and status of the P versus NP question (Gödel’s 1956 letter, Edmonds)](https://www.cs.columbia.edu/~tal/3261/sipserpnp.pdf); [ACM A.M. Turing Award: Stephen A. Cook (1982)](https://amturing.acm.org/award_winners/cook_n991950.cfm); [Wikipedia: Karp’s 21 NP-complete problems](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems); [William Gasarch (2019): The third P =? NP poll](https://www.cs.umd.edu/users/gasarch/papers/poll3.pdf); [Wikipedia: P versus NP problem (consequences)](https://en.wikipedia.org/wiki/P_versus_NP_problem)