OpenAI’s ETH claim: what it means for P vs NP

On October 26, 2026, OpenAI announced an AI-generated result that it says refutes the Exponential Time Hypothesis, or ETH. Researchers use this conjecture to reason about how difficult certain computing problems must be. OpenAI says hundreds of papers have used it to establish conditional limits on algorithms.

The company published a natural-language writeup and a Lean formalization, a version expressed for computer verification. Its accompanying technical documentation describes a subexponential-time algorithm for counting the solutions to a family of Boolean logic problems. That is the specific claim behind the headline.

An external group led by Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams is examining and explaining the work. OpenAI describes participation as “voluntary and unpaid,” with conclusions belonging to the researchers. The released materials give experts something concrete to inspect; the company’s announcement alone does not establish scientific consensus.^[2][3]

The idea, explained

Start with a puzzle. Checking a completed Sudoku is straightforward: inspect the rows, columns, and boxes. Finding the solution can require much more searching. P vs NP turns that difference into a precise question about how the work grows as a problem gets larger. P contains problems solvable in polynomial time, meaning the work is bounded by a fixed power of the input size; NP contains problems whose proposed solutions can be checked in polynomial time. Every problem in P is also in NP. The unresolved question is whether NP contains anything outside P.

ETH asks a more specific question about 3-SAT. Imagine a row of on/off switches and a collection of rules. Each rule says that at least one of three conditions must hold, such as switch A being on, B being off, or C being on. Can you choose settings that satisfy every rule? Trying every setting means checking 1,024 combinations for 10 switches and 1,048,576 for 20. Those counts illustrate brute force, not a claim that every algorithm must try every combination.

ETH says, roughly, that there is no general subexponential-time algorithm for 3-SAT. Refuting it would show that the problem can be solved with a slower rate of growth than that conjecture allows. But subexponential does not automatically mean polynomial, and a better theoretical growth rate does not automatically mean a useful runtime on real inputs.

That is why an ETH refutation would not itself settle P vs NP. It challenges a more specific proposed limit. Clay Mathematics Institute still lists P vs NP as unsolved, and OpenAI explicitly says that turning the theoretical work into practical improvements requires further research.^[1][2][3]

“For now, it's a claim, not a confirmed result.” Watch at 3:38 ↗

I separate three milestones: a claimed mathematical result, expert understanding of that result, and software people can actually use. Keeping them distinct makes room for both the possible significance and the remaining uncertainty.

If the claim survives examination, results whose hardness guarantees depend on ETH would need another look. That does not invalidate unrelated research or supply a ready-made speedup for every difficult task. The important follow-up is what researchers can explain, verify, and build from the proof.^[2]

What to take away

When the next breakthrough headline appears, identify the exact problem and the claimed improvement. Ask whether the source reports a proof, a formal verification, an external assessment, or a working implementation. Each answers a different question.

For this result, follow the public examination of the proof and any later work connecting it to usable algorithms. The meaningful change would be a revised understanding of computational difficulty. A faster laptop is a separate engineering outcome.^[2][3]