OpenAI’s Exponential Time Hypothesis Disproof Explained: What It Is, How It Works, Limits and Risks

Last updated: 27 October 2026

On Monday, 26 October 2026, OpenAI made one of the boldest claims any AI company has made about research: that one of its internal models has disproved the Exponential Time Hypothesis (ETH), a 25-plus-year-old conjecture at the heart of theoretical computer science. The model reportedly found the argument on 16 October, it was checked in the Lean proof assistant the next day, and the manuscript, titled “The Exponential Time Hypothesis is False”, is now public in OpenAI’s openai/math GitHub repository.

In the same announcement OpenAI also claimed AI-produced results on the local smoothing and Kakeya conjectures in harmonic analysis and on the existence of quantum field theories such as quantum chromodynamics in physics. Those are huge claims too, but the ETH result is the one every computer science student should pay attention to, because it touches the exact ideas you study in algorithms and theory of computation: SAT, exponential time, reductions and lower bounds.

In this post I explain what ETH is in plain language, what OpenAI actually claims (including the precise running time, which several reports got slightly wrong), how the result is being checked, what it does and does not change, and why I think this is a defining moment for how Indian students should think about AI and mathematics. One thing up front: this is a claim, not yet an accepted theorem. Independent review has only just begun.

Quick summary

• What happened: On 26 October 2026 OpenAI announced that an unnamed internal model produced a disproof of the Exponential Time Hypothesis, with a Lean formalisation and a manuscript posted on GitHub.
• The claim in one line: A deterministic, polynomial-space algorithm that exactly counts the satisfying assignments of a k-CNF formula (for any fixed k, including 3-SAT) in subexponential time.
• The running time: The manuscript states roughly 2^{O(n·log log n / √log n)} times a polynomial factor. The Lean-checked statement proves a slightly weaker bound with (log log n)² in place of log log n.
• Who is checking it: Russell Impagliazzo and Ramamohan Paturi (UC San Diego), two of the people who originally proposed ETH, and Ryan Williams (MIT) are leading an open examination. They have said their involvement is not an endorsement.
• What it does not do: It does not prove P = NP, it does not break cryptography, and it gives no practical speed-up for real SAT solvers.
• Status: Unconfirmed. Treat it as a serious, checkable claim under review.

What is the Exponential Time Hypothesis, in plain language?

Start with 3-SAT. You are given a Boolean formula in conjunctive normal form where every clause has at most three literals, for example (x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₄ ∨ x₂) ∧ … The question is whether some true/false assignment to the n variables makes the whole formula true. You know it from your propositional logic classes, and you know it as the first famous NP-complete problem.

Brute force tries all 2ⁿ assignments. Clever algorithms do better: the best known ones for 3-SAT run in roughly 1.3ⁿ time. But every known algorithm is still exponential, that is, of the form cⁿ for some constant c greater than 1.

The Exponential Time Hypothesis, proposed by Impagliazzo and Paturi around 1999, says this is unavoidable: there is some constant δ > 0 such that no algorithm solves 3-SAT in time 2^δn. In other words, 3-SAT has no subexponential algorithm, nothing like 2^√n or 2^{n/log n}.

Two related ideas are worth knowing:

• ETH is stronger than P ≠ NP. If ETH is true then P ≠ NP. But ETH being false does not make P = NP, because a subexponential algorithm can still be far slower than any polynomial.
• SETH, the Strong Exponential Time Hypothesis, says that as the clause width k grows, the best exponent for k-SAT approaches brute force. SETH implies ETH, so if ETH is false, SETH falls with it.

Why ETH matters so much

ETH is not just one conjecture; it is a foundation stone. Over the past two decades researchers have used it, through reductions, to explain why many problems seem to resist fast algorithms. Assuming ETH, problems such as graph colouring, Hamiltonian cycle, maximum clique, independent set and vertex cover have no subexponential algorithms, and finding a k-clique needs roughly n^Ω(k) time. Whole areas, including parameterised complexity and fine-grained complexity, use ETH and SETH to prove “conditional lower bounds”: statements of the form “if ETH holds, you cannot do better than this”.

OpenAI’s own announcement notes that ETH has underpinned hundreds of papers. If it is false, those papers are not wrong (a statement like “if ETH then X” stays logically true), but many of them lose their supporting assumption, and researchers will need to work out which results can be rebuilt on weaker hypotheses. That is why theorists are taking this claim very seriously, and also very carefully.

What exactly does OpenAI claim?

Here are the claims, as stated in OpenAI’s announcement, the manuscript and the Lean scope document:

A note on accuracy: some news summaries described the running time as “about 2^{n/√log n}“. Ryan Williams summarised it on social media as roughly exp(n/(log n)^1/2+o(1)), which is a fair compact way of writing the manuscript bound. The extra log log n factor is small but real, and the Lean statement carries a slightly larger factor, so if you are writing about this, quote the bound from the primary documents.

How is the claim being checked?

There are two separate layers of checking, and it helps to understand both.

1. Machine checking with Lean

Lean is a proof assistant: a programming language in which mathematical statements and proofs are written so precisely that a computer can verify every logical step. If Lean accepts a proof, the formal theorem follows from the formal definitions. This is far stronger evidence than a long natural-language paper that nobody has read yet.

But Lean only certifies what was actually written down. The big question for experts is whether the formal statement truly captures “3-SAT is solvable in subexponential time” on a standard model of computation, with the right encoding of inputs and the right notion of running time. Several reports, including Tech Insider’s, make exactly this point: a Lean check confirms the formal statement, not automatically the headline. OpenAI’s scope document defines the machine model, the input encoding and the space bound, and that is precisely the part reviewers will scrutinise.

2. Human review by the people who invented ETH

OpenAI asked outside experts, which it calls “shepherds”, to organise scrutiny of each result. For ETH, the group is led by Impagliazzo, Paturi and Williams. According to The Next Web, the three said publicly that their involvement “should not be taken as certification of the claim”, that they signed no non-disclosure agreements and are not being paid, and that they asked OpenAI to release all raw data on the result and to fund a conference for the research community. Both Williams and OpenAI say OpenAI agreed. The three also wrote that if the claim is right, it will change an important part of theoretical computer science.

Separately, OpenAI says it has given $5 million to the Simons Foundation for workshops, conferences and programmes on understanding AI-produced results, and that it does not seek academic credit for the results themselves.

What it changes, and what it does not

If the result survives review, here is a sober view of the consequences.

To see why there is no practical impact, try a rough calculation. Ignore the hidden constants (which we do not know) and use base-2 logarithms. For n = 1,000 variables, n·log log n / √log n works out to slightly more than 1,000, so the bound is no better than brute force at that size. To beat the roughly 1.3ⁿ of today’s best algorithms, n would have to exceed something like 2⁶⁰⁰, a number with about 180 digits. This is purely an illustration, but it shows the point: the result is about asymptotic behaviour, the shape of the curve as n goes to infinity, not about solving your next SAT instance faster.

Limits, criticism and open questions

I want to be balanced here, because the hype around AI and maths is intense.

• No independent confirmation yet. Every outlet covering this, from The Next Web to ANI (via The Tribune), describes these as OpenAI’s claims. The reviewers have been explicit that they are not certifying anything yet.
• Early community reaction is cautious. Discussion on forums such as Hacker News has been largely sceptical, which is the healthy default for a claim this large.
• Formal statement fidelity. As explained above, the gap between “Lean accepts this theorem” and “ETH is false” depends on definitions that experts must check.
• The model is a black box. OpenAI has not named the model or described how it was prompted or how much compute was used, which makes it hard to judge how repeatable this kind of discovery is.
• Independence questions. Some commentators have noted that OpenAI chose the shepherds. The ETH group’s public conditions (no NDA, no payment, full data release) are a strong answer to that concern, but it is a fair question to keep asking.
• Uneven release across results. The ETH and harmonic analysis materials are public. The physics materials have been held back by the group led by Nobel laureate David Gross, which will prepare its own account first.
• A track record still being built. OpenAI’s earlier large release of AI-generated maths papers on 6 October drew criticism from some mathematicians, including Terence Tao, according to OfficeChai. Each new claim is judged on its own merits, but that history is one reason for caution.

The bigger question: credit, verification and trust

This episode raises questions that go beyond one conjecture. Who gets credit when a machine finds a proof and humans spend months checking and explaining it? The ETH reviewers warned that credit could flow to whoever publishes first or owns the most powerful tools, while the slower work of verification and explanation is undervalued. Mathematicians raised similar concerns in the Leiden declaration in June 2026.

There is also a question of access. If frontier results depend on internal models that only a few companies have, how do universities, including Indian institutions, take part on equal terms? OpenAI’s choice to publish the Lean files and fund open conferences helps, but the underlying asymmetry remains. For researchers and students, the practical lesson is that the ability to verify, formally or by careful reading, is becoming as valuable as the ability to discover.

Why this matters for Indian students and educators

You might think a complexity theory result has nothing to do with your exam preparation. I think the opposite is true.

• GATE CS and GATE DA fundamentals: The GATE 2027 CS syllabus does not list P, NP or SAT by name, but it does include asymptotic worst-case time and space complexity in Algorithms, propositional logic in Discrete Mathematics, and Turing machines and undecidability in Theory of Computation. Understanding why 2^{n/√log n} is subexponential but superpolynomial is exactly the kind of asymptotic reasoning GATE rewards.
• University courses: Design and Analysis of Algorithms and Theory of Computation courses at most Indian universities cover NP-completeness and reductions. This news is a perfect classroom case study, and I would encourage teachers to use it.
• Interviews and research careers: Questions about SAT, reductions and complexity classes come up in M.Tech and PhD interviews at IITs, IISc and research institutes. Being able to explain ETH, SETH and why this claim matters will set you apart.
• Formal verification is a skill: Lean and similar tools are increasingly used for checking proofs and verifying software and hardware. Learning the basics of a proof assistant is a genuine career differentiator for students interested in formal methods, compilers or security.
• AI literacy: This is a concrete example of AI systems doing frontier research, and of the human role shifting toward checking, explaining and judging. That shift will reach data science and software engineering too.

My advice: do not read this as “AI will do all the thinking, so why learn theory?” Read it as the reverse. When a machine claims to have overturned a hypothesis, the people who matter are the ones who can tell whether it is right.

Frequently asked questions

Has OpenAI proved that P = NP?

No. The claimed algorithm is subexponential, but it is still slower than any polynomial. P versus NP remains open.

Is the Exponential Time Hypothesis now officially false?

Not yet. OpenAI claims it, and the proof has been checked in Lean, but independent experts are still examining whether the formal statement matches ETH and whether the argument holds. Until that review reports, treat it as unconfirmed.

Does this break encryption or make SAT solvers faster?

No to both, as far as anyone can tell today. Cryptography does not rest on the worst-case hardness of 3-SAT, and the bound only beats existing algorithms for astronomically large inputs.

What is Lean, and can I try it?

Lean is an open-source proof assistant and programming language for writing machine-checked mathematics. It is free to install, and the openai/math repository includes the Lean files for this claim, though they are written for experts. Beginners should start with introductory Lean tutorials before attempting to read research formalisations.

Which OpenAI model found the result?

OpenAI has not said. Its announcement refers only to its internal models.

Is this in the GATE syllabus?

Not directly. But the underlying concepts (asymptotic complexity, propositional logic, computability) are, and the topic is common in university algorithms courses and research interviews.

The bottom line

If OpenAI’s claim survives review, it will be remembered as the moment an AI system overturned a central conjecture of computer science. If it fails, it will be a valuable lesson in why formal statements and human scrutiny matter. Either way, the process itself, a model’s output, a Lean check, and an open examination led by the very people who proposed the hypothesis, is a preview of how research may work from now on. My suggestion for students is simple: learn the fundamentals well enough to follow that review as it unfolds. It is one of the best free lessons in algorithms you will ever get.

Sources and further reading

• OpenAI: Building scientific understanding with academic communities (26 October 2026)
• OpenAI math repository on GitHub (manuscripts and Lean files)
• openai/math: Lean scope notes for the ETH result
• The Next Web: OpenAI claims ETH is false, plus Kakeya and Yang-Mills results
• Ryan Williams on the claimed running time
• AI TLDR: OpenAI says its model refuted the Exponential Time Hypothesis
• AI Weekly: OpenAI hands ETH, Kakeya and Yang-Mills proofs to reviewers
• Tech Insider: OpenAI’s three science claims
• The Tribune (ANI): AI models have produced proofs challenging major theories
• OfficeChai: New OpenAI research says ETH is false
• Wikipedia: Exponential time hypothesis (background)
• GATE 2027 CS syllabus (IIT Madras)

Written by Piyush Wairale (M.Tech, IIT Madras), founder of PiyushAI Edtech. This is a fast-moving story and the review is ongoing; figures and statements are as reported on or before 27 October 2026.