Takeaway: On October 26, 2026, OpenAI said an internal model had refuted the Exponential Time Hypothesis (ETH) — a late-1990s conjecture that deciding 3-SAT on n variables takes 2Ω(n) time in the worst case. The company published a natural-language write-up, dated October 25, and a Lean formalization. Russell Impagliazzo and Ramamohan Paturi of UC San Diego — two of ETH’s original proposers, with Francis Zane — and MIT’s Ryan Williams are organizing an independent examination. They have been explicit that their involvement is not a certification. In a November 6 New York Times report by Cade Metz, Impagliazzo called the claim “very shocking news,” and also a shock “that the work was not done by a human being.”
This is a complexity-theory story about a claimed algorithm and the review now underway. It is not the same topic as today’s note on OpenAI’s security partnership with Hacktron, or this morning’s METR assessment of Anthropic’s AI R&D pace. Those pieces were about product security and research productivity. This one is about whether a pillar of fine-grained complexity theory has actually fallen, and what the paper does not say about P versus NP or today’s cryptography.
What the Exponential Time Hypothesis claims
ETH is a working assumption, not a theorem. In the version OpenAI restates, deciding whether a 3-SAT formula on n variables is satisfiable requires 2Ω(n) time in the worst case: the runtime grows exponentially with the number of variables, and no clever algorithm removes that exponential dependence. Impagliazzo, Paturi, and Zane introduced the hypothesis in the late 1990s. Hundreds of later papers have used it to argue that problems in graph theory, computational biology, databases, computational geometry, and other fields cannot be solved much faster than the obvious exponential search.
ETH sits next to, but is not the same as, the Clay Mathematics Institute’s P versus NP question. P versus NP asks whether every problem whose solutions are easy to check is also easy to solve. ETH is a more specific bet about 3-SAT: even if P ≠ NP, 3-SAT might still have a slightly-subexponential algorithm — or it might not. A refutation of ETH would show that 3-SAT can be solved (or, in OpenAI’s write-up, counted) in 2o(n) time. That is still superpolynomial. It would not prove that P = NP, and it would not by itself hand anyone a practical SAT solver for industrial instances.
What OpenAI says the model found
The public write-up is titled The Exponential Time Hypothesis is False. Its abstract gives a deterministic algorithm that exactly counts the satisfying assignments of an arbitrary k-CNF formula. For every fixed k ≥ 2, on a formula with n variables and m clauses, the claimed runtime is (n + m)Ok(1) · 2n / (log n)1/2 + o(1), using space polynomial in n and m.
Two details in that statement matter:
- The algorithm counts solutions (#k-SAT), which is a stronger task than answering yes or no. A counting algorithm also decides satisfiability, so the 3-SAT case would be enough to refute ETH.
- The exponent is n divided by a slowly growing function of n, not a smaller constant times n. That is subexponential — it beats every bound of the form 2εn for a fixed ε > 0, once n is large enough — but it is nowhere near polynomial time.
OpenAI says the model produced the natural-language disproof on October 16, 2026, and that the company formalized the result in Lean the next day. Lean is a proof assistant: if a development compiles, the logical steps inside the formalized theorems check out relative to the definitions those theorems use. That is not the same thing as a human reviewer confirming that the formalized statement is the same claim the prose paper makes, or that the paper’s sharper bound matches the Lean file.
In fact, notes attached to the public Lean release say the formalized bound is slightly weaker than Theorem 1.1 in the October 25 write-up — still subexponential, with extra log-log factors in the exponent — and that nobody has certified a match between the Lean statements and the paper’s claims. Treat the preprint and the Lean development as two related artifacts under review, not as a single already-checked proof.
Who is checking it, and what they have said
OpenAI asked Impagliazzo, Paturi, and Williams to help shepherd an open examination. All three are specialists in algorithms and complexity; Williams has previously refuted stronger variants of ETH and also used ETH in hardness results. The company says it agreed to two requests from the group: publish the raw materials so anyone can inspect them, and fund a conference on the result’s implications.
Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny.
Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams, as quoted by The Next Web, October 26, 2026
Williams also said the group signed no nondisclosure agreements and is not being paid, according to the same report. OpenAI’s own post lists four principles for these collaborations: transparency, no academic credit for OpenAI on the discoveries, recognition for the people who explain the results, and independence — participants speak for themselves, not for the company.
The November 6 Times story is what brought the claim back into wider circulation almost two weeks later. Metz quotes Impagliazzo comparing the P versus NP intuition to Sudoku: finding a solution can be painfully hard, while checking one is easy. ETH was the more specific version of that intuition for 3-SAT. If the new algorithm holds up, Impagliazzo said, a really fast Sudoku solver could in theory be used to design optimal circuits. He framed the deeper question as whether impressive shortcuts exist that avoid enumerating every candidate. Williams told the Times there are no immediate practical applications. Turning a theoretical runtime of this shape into something engineers would run on real formulas, chips, or proteins would take years of further work — if the proof survives review at all.
What this does not mean
A careful reading of OpenAI’s post and the paper’s abstract already rules out several headlines the claim will keep attracting:
- It is not a solution to P versus NP. A 2o(n) algorithm can still grow faster than every polynomial. OpenAI describes ETH as “deeply related” to P versus NP, not as a substitute for that question.
- It does not say every NP problem now has a subexponential algorithm. The write-up’s headline result is about fixed-width k-CNF counting. Reductions that blow up the number of variables can erase a 2o(n) gain.
- It is not an announced break of the encryption people use today. Williams’s “no immediate practical applications” line is the responsible summary. A subexponential algorithm for 3-SAT, even if correct, is not the same thing as factoring RSA moduli or attacking AES on a laptop this year.
- A Lean file is not peer review. Machine-checked steps are valuable. Reviewers still have to confirm that those steps prove the intended theorem, that the intended theorem is ETH as the field states it, and that no gap hides in definitions or encoding assumptions.
A concurrent claim from Anthropic — and two other OpenAI results
The Times reported that Anthropic said it too had disproved ETH, shortly after OpenAI’s announcement. Later coverage, including a Scientific American report dated October 27, treated the two write-ups as independent, concurrent claims. We have not audited Anthropic’s manuscript here. The point for readers is simply that two frontier labs posted claimed 2o(n) algorithms for 3-SAT in the same news cycle, and that neither claim is a finished, community-certified theorem.
OpenAI’s October 26 post actually announced three results and tried a different disclosure path for each:
- Mathematics: a claimed proof of Christopher Sogge’s 1991 local smoothing conjecture in every dimension, which OpenAI says would also settle the Kakeya conjecture and Stein’s restriction conjecture in all dimensions. The company released a write-up and a Lean proof, following the same public-dump approach as its October 6 math release.
- Computer science: the ETH claim, with public materials and an external examination group.
- Physics: a claimed existence proof for certain four-dimensional quantum field theories, including quantum chromodynamics, plus (as a subproblem) pure Yang–Mills theory — part of a Clay Millennium Prize problem. A group led by Nobel laureate David Gross, including Michael Douglas, Arthur Jaffe, Igor Klebanov, and Nikita Nekrasov, asked OpenAI to hold the AI-produced artifacts while the group writes the work up itself.
OpenAI also points to a $5 million contribution to a Simons Foundation initiative for workshops on AI-produced results. The company says it does not seek academic credit for what its internal models find.
What this is — and what it is not
| Claim | Status | Notes |
|---|---|---|
| OpenAI announced a claimed ETH refutation on October 26, 2026 | Confirmed | Company blog; write-up dated October 25 |
| An internal model produced the natural-language argument on October 16 and a Lean formalization on October 17 | Stated by OpenAI | The model is not named |
| The paper claims a deterministic, polynomial-space #k-SAT algorithm with runtime (n+m)Ok(1) 2n/(log n)1/2+o(1) | Confirmed as the abstract’s statement | For every fixed k ≥ 2 |
| This proves P = NP | No | The claimed algorithm is subexponential, not polynomial |
| Impagliazzo, Paturi, and Williams have certified the proof | No | They said their involvement is not certification |
| Impagliazzo called the claim shocking in November 2026 coverage | Confirmed as reported | Cade Metz, The New York Times, November 6, 2026 |
| Williams said there are no immediate practical applications | Confirmed as reported | Same Times article |
| The Lean file is identical to the paper’s sharpest bound | Not established | OpenAI’s Lean scope note describes a slightly weaker — still subexponential — formalized bound |
| Anthropic posted a concurrent claimed 3-SAT speedup | Reported by the Times and later outlets | We did not independently verify Anthropic’s manuscript for this article |
| Today’s encryption is publicly broken by this announcement | No | That is not what OpenAI claimed, and Williams said there are no immediate applications |
FAQ
Has ETH actually been disproved?
OpenAI claims it has, and it published a write-up plus a Lean development. The researchers who proposed ETH are helping organize a review and have said that work is not a certification. Until that examination — and broader independent scrutiny — finishes, the responsible status is “claimed refutation under review,” not “settled theorem.”
Did an AI solve P versus NP?
No. ETH is a conjecture about the exponential cost of 3-SAT. Even a correct 2o(n) algorithm would leave P versus NP open. Polynomial time is a much stronger demand than subexponential time.
Why are people talking about chip design and cryptography?
Because many theoretical reductions start from SAT-like problems. Impagliazzo told the Times that a genuinely fast Sudoku-style solver could, in principle, help design optimal circuits, and commentators have sketched longer-range effects on cryptography and drug design. Those are hypothetical consequences of a verified, then engineered, algorithm — not capabilities anyone has demonstrated with this write-up.
If Lean checked the proof, why is there still a review?
Lean checks the inferences inside a formal development against the definitions in that development. Reviewers still have to read those definitions, compare them with the paper and with the standard statement of ETH, and look for encoding or model-of-computation mismatches. OpenAI’s own Lean notes already flag that the formalized bound is not word-for-word the paper’s sharpest bound.
Is this the same news as OpenAI partnering with Hacktron?
No. The Hacktron note covers a November security partnership aimed at finding vulnerabilities in OpenAI’s own systems and third-party connections. This article is about an October complexity-theory claim that returned to wider attention after the November 6 Times report.
Sources: OpenAI — Working with academic communities to build scientific understanding (October 26, 2026); The Exponential Time Hypothesis is False (OpenAI math preprint, October 25, 2026); The Next Web — OpenAI says its AI model has disproved the Exponential Time Hypothesis (October 26, 2026); Cade Metz, “How A.I. Just Blew Up a Key Tenet of Computer Science,” The New York Times, November 6, 2026. Quotations from Impagliazzo and Williams in the Times are taken from that report. We have not independently verified the Lean development or the correctness of the claimed algorithm.