News
What Is the Exponential Time Hypothesis? OpenAI’s Claim, Explained
The Exponential Time Hypothesis (ETH) says some problems can’t be solved much faster than brute force. OpenAI now claims its AI proved ETH false. What that means.
The Exponential Time Hypothesis was a quiet corner of computer science until this week. On October 26, 2026, OpenAI said its AI models had produced a proof that the hypothesis is false. That is a big claim, because hundreds of research papers assume it is true.
So what is the Exponential Time Hypothesis, what exactly did OpenAI say, and does it change anything for normal people? Here is the plain-English version, with the parts that are still unconfirmed clearly marked.
What is the Exponential Time Hypothesis?
Start with a puzzle. You have a list of on/off switches and a list of rules like “switch 1 is on, or switch 4 is off, or switch 7 is on.” Can you set every switch so all the rules are happy at once? That is the satisfiability problem, called SAT. When every rule mentions at most 3 switches, it is called 3-SAT.
The obvious way to solve it is brute force: try every combination. With n switches there are 2n combinations. Add one switch and the work doubles. That is what “exponential time” means.
Smart tricks can cut the work, but every known trick still doubled the work at a steady rate as the puzzle grew. The Exponential Time Hypothesis says that is unavoidable: no method can solve 3-SAT in “subexponential” time, meaning a time that grows slower than any steady doubling. Impagliazzo and Paturi proposed it in 1999, and it became a standard assumption, used to argue that problems in graph theory, databases, computational biology and geometry cannot be solved much faster than we already do.
Is the Exponential Time Hypothesis false? What OpenAI claims
OpenAI says yes. Its paper is titled simply “The Exponential Time Hypothesis Is False,” listed with OpenAI as the author. It describes a deterministic algorithm that counts every satisfying setting of a k-SAT puzzle (with k at least 2), using only a modest amount of memory. If the count is zero, the puzzle has no solution, so the same method also answers the yes/no question.
The claimed running time is roughly 2 to the power of n divided by (log n)1/2, plus some smaller terms. That exponent still grows almost as fast as n, but it grows a little slower than any steady doubling rate. That small gap is all it takes to break ETH. According to the paper’s summary, it would also knock out several stronger cousins: the Strong Exponential Time Hypothesis (SETH), Gap-ETH and NSETH.
The timeline OpenAI gave, as reported by Unite.AI: its system produced the written disproof on October 16, a Lean formalization followed on October 17, and the material was published on GitHub on October 26.
| OpenAI’s October 26 claim | Field | Who is checking it | What is public |
|---|---|---|---|
| The Exponential Time Hypothesis is false | Computer science | Russell Impagliazzo and Ramamohan Paturi (UC San Diego), Ryan Williams (MIT) | AI-written paper and Lean proof on GitHub |
| Sogge’s local smoothing conjecture holds in every dimension | Mathematics | Open to the research community | AI-written proof and Lean proof on GitHub |
| Existence proof for 4D gauge theories, including Yang–Mills and QCD | Physics | A group led by Nobel laureate David Gross | Not released; the group will write it up |
Has the proof been verified?
Not yet. Three things are true at the same time:
- A computer checked it. OpenAI says the proof was formalized in Lean, software that checks every logical step. That is much stronger than a human skim.
- That is not the final word. As StartupHub.ai notes, Lean confirms the proof of the statement as it was typed into Lean. Experts still need to confirm that statement truly matches the real hypothesis, with no gap in the definitions.
- The right people are looking. The checking group is led by the two researchers who proposed ETH, plus Ryan Williams of MIT, known for work linking faster algorithms to lower bounds. OpenAI says it will make the raw data public and fund a conference on what the result means.
Until that group reports back, treat “ETH is false” as a serious, computer-checked claim, not a settled fact.
Exponential Time Hypothesis vs P vs NP
People often mix these up. P vs NP asks whether hard puzzles like SAT can be solved in “polynomial” time, the kind of speed computers handle well. ETH makes a stronger bet: not only is SAT not fast, it is truly exponential. If ETH is false, it means SAT is slightly less hard than people thought. It does not mean SAT is easy. The claimed algorithm is still far slower than polynomial, so P vs NP stays open, and the paper’s own summary says it does not give fast algorithms for NP problems in general.
Why does it matter?
Engadget points out that ETH underpins hundreds of papers. Many results say “if ETH is true, this problem cannot be solved faster than X.” If ETH falls, those statements lose their support, and researchers can look for better algorithms in places they had given up on.
It will not make your phone faster next week. OpenAI itself says turning these theory results into practical gains will take a lot more research. The bigger story is who found it. This is one of three results OpenAI announced on the same day, after a large batch of AI-written math papers it released on October 6. It fits the trend we covered in What is TasteVal?: AI is moving from answering questions to doing research.
What this means for you
You do not need to care about 3-SAT. But the way this result was made is worth noticing. The model did not write one clever answer. It worked through a long chain of steps, then a separate checker (Lean) tested every step before anyone called it done. Plan, work, check: that is the agent pattern, explained in What is agentic AI?
The same pattern is useful for ordinary tasks. A trip plan, a hard email or a budget comes out better when one agent drafts and another checks. That is what a multi-agent app on your iPhone does for you, without you having to pick a model or write a careful prompt.
Quick answers
What is the Exponential Time Hypothesis in simple terms? It is the bet that the 3-SAT logic puzzle cannot be solved much faster than trying every combination, so its difficulty doubles at a steady rate as it grows.
Who came up with the Exponential Time Hypothesis? Russell Impagliazzo and Ramamohan Paturi proposed it in 1999, and it was developed further with Francis Zane.
Is the Exponential Time Hypothesis false? OpenAI claims so, in a paper posted October 26, 2026 and checked in Lean. Independent experts, led by Impagliazzo and Paturi, have not finished verifying it.
Where is the OpenAI exponential time hypothesis paper? OpenAI published the AI-written paper and its Lean proof on its public GitHub math repository, and the paper also appears on alphaXiv as “The Exponential Time Hypothesis Is False.”
Does disproving ETH solve P vs NP? No. The claimed algorithm is still much slower than polynomial time, so P vs NP remains open.
What is the Strong Exponential Time Hypothesis? SETH is a stricter version of ETH about general k-SAT. OpenAI’s paper says its algorithm would refute SETH too.
New to the vocabulary? Our agentic AI glossary covers terms like frontier models, tool use and agents in plain English. For the model family behind OpenAI’s recent math push, see What is GPT-6 Astra? (OpenAI has not said which model produced this proof.)
Sources: OpenAI: Working with academic communities to build scientific understanding · Engadget · Unite.AI · StartupHub.ai · alphaXiv: The Exponential Time Hypothesis Is False · Wikipedia: Exponential time hypothesis
