Result
Exponential Time Hypothesis: AI Refutation Claims Tracked
What the exponential time hypothesis says, what OpenAI and Anthropic claim, the bounds side by side, and how far each claim is checked as of November 2026.
Last checked:
What is being claimed
The exponential time hypothesis, or ETH, is a conjecture about how fast 3-SAT can be solved. In late October 2026, OpenAI and Anthropic each published a paper claiming an algorithm that refutes it, with credit given to their AI models. Neither claim has a peer-reviewed publication that we could find as of November 1, 2026. The researchers organizing the public examination of OpenAI's claim have said their involvement does not certify it. This page reports those claims and does not judge them.
ETH here means the complexity hypothesis, not Ethereum or ETH Zurich. See the full ledger for related results, including 3SUM and APSP.
What ETH says
3-SAT asks whether a formula made of clauses with at most three literals has a satisfying assignment. Trying every assignment takes about 2n steps for n variables. Impagliazzo and Paturi defined sk as the infimum of δ such that k-SAT has an algorithm running in O(2δn) time. ETH says sk is greater than 0 for k at least 3, so 3-SAT would need time exponential in n, with some positive constant. (1999 paper)
Many hardness results in complexity theory assume ETH or the stronger SETH, so the claim matters beyond 3-SAT itself. Before these papers, the best 3-SAT records Anthropic cites were O(1.328n) deterministic and O(1.308n) randomized.
The bounds, side by side
These are copied as written and not normalized. They differ in setting, in whether they count or decide, in whether they state a space bound, and in machine model, so don't compare them as if they were one number.
| Source | Setting | Bound, as written |
|---|---|---|
| OpenAI manuscript, abstract | Fixed k ≥ 2, n variables, m clauses; counting | (n + m)^{O_k(1)} 2^{n/(log n)^{1/2+o(1)}} |
| OpenAI manuscript, Theorem 1.1 | General, n ⩾ 20 declared variables | (n + m)^{O_k(1)} 2^{O_k(n log log n/√log n)} bit operations; (n + m)^{O_k(1)} bits of space |
| OpenAI manuscript, Theorem 1.1 | Sparse: m ⩽ Dn for fixed D > 0 | (n + m)^{O_{k,D}(1)} 2^{O_{k,D}(n/√log n)} |
| OpenAI Lean scope note, docs/378 | Fixed k ≥ 2, canonical encoding of bit length L | time (L+1)^{O_k(1)} 2^{O_k(n(log log n)^2/√(log n))}; visited cells (L+1)^{O_k(1)} |
| Anthropic paper, Theorem 1 | k-CNF with m clauses in which n variables occur | 2^{O(min{k^2 n log log n/√log n, km/√log m})} |
| Anthropic paper, Theorem 2 | 3-CNF on n variables, any number of clauses; algorithm depends on δ | O(2^{δn}) for every δ > 0 |
| Anthropic Lean, MainTheorem | One Turing.FinTM2 machine, one C; k ≥ 1, m ≥ 2, n ≥ 4, every variable occurs, no repeated clause; log is base 2 | ⌊(2 : ℝ) ^ ((C : ℝ) * min (expM k m) (expN k n))⌋₊; expM = k·m/√(lg m); expN = k²·n·lg(lg n)/√(lg n) |
| O'Donnell exposition, Theorem 6.1 | Deterministic permanent with O(1) nonzeros per row and column; sparse 3-CNF | 2^{O(n(log log n)^2/√log n)} |
| O'Donnell exposition, Theorem B.1 | Arbitrary 3-CNF; randomized, exact with probability at least 3/4 | 2^{O(n(log log n)^3/√log n)} |
| Kintali exposition, Theorem 1.1 | Deterministic 3-SAT; fixed ε > 0 | C_ε (n + m + 1)^{c_ε} 2^{εn} bit operations |
How far it has been checked
- Claim: OpenAI's manuscript and Anthropic's paper. Anthropic's paper says an internal Claude model found the core algorithm with no human input. OpenAI's repository attributes its manuscripts to an unnamed internal model.
- Lean: OpenAI's scope note describes a formalized bound with a weaker (log log n)2 factor than Theorem 1.1. Anthropic's Lean file states its main theorem and the negation of ETH on Mathlib multi-stack machines.
- Do the Lean statements say ETH is false? Carlos Toledo reports bridging each statement to a Lean version of textbook ETH in that lab's machine model, leaving the step to standard models in prose. His tools and bridge proofs were written with Claude, Anthropic's model, and Claude Opus 5.5 wrote the first of his two statement readings. He says kernel acceptance does not establish that ETH is false. Totó Busnello reports replaying both proofs and reading both statements by hand, with one encoding check unfinished. He says he did not compare Anthropic's statement with its paper.
- People: Impagliazzo, Paturi and Williams wrote that their participation in examining OpenAI's claim is not certification, and asked for independent scrutiny. Lance Fortnow wrote that he had not checked the proof himself but considers it safe to assume ETH is finished.
- Peer review: none found as of November 1, 2026.
What it does not mean
Each of these is a statement by the person or paper named.
- P versus NP is not settled. Anthropic's paper says the result does not directly bear on it. Scott Aaronson wrote that refuting ETH stays far from P=NP.
- SAT solvers don't get faster. Anthropic's paper calls its result purely asymptotic, saying its bound beats 2n only for n above 1010 000 when m = 5n.
- Subset Sum and Traveling Salesman don't follow. Fortnow wrote that reductions to 3-SAT inflate the variable count too much to help them.
- No broken cryptography is reported in these sources. Aaronson said he has no news of any code being broken. Ryan Williams told TechCrunch that a faster algorithm could mean some key sizes count as broken, then relayed that OpenAI apparently checked and was reasonably confident no break followed. That is OpenAI's own assessment. OpenAI's manuscript says its result rules out 2^Ω(n) inversion hardness for Goldreich-style one-way candidates with constant locality, and that polynomial-time one-wayness stays open.
- The Orthogonal Vectors hypothesis is not claimed refuted. Anthropic's paper says so, and Williams wrote that the full hypothesis remains open to his knowledge.
What changes if it holds
- The implications aren't refuted, but one premise goes. Fortnow notes that a false ETH doesn't make its former consequences false. OpenAI's manuscript says the refutation takes away ETH and SETH as one basis for those hardness claims, and that some bounds still follow from weaker hypotheses such as the Orthogonal Vectors Conjecture.
- Many papers would need another look. Anthropic's paper reports that a Claude-run search counted over 800 papers with a result proved only under ETH or hypotheses implying it. Williams told TechCrunch that many such papers would need revisiting.
- How much survives is disputed. Aaronson guesses nearly all ETH-based results can be saved, for now, under a slightly weaker ETH. Michael Lampis replied that this is too optimistic, since some distinctions need finer formulations.
- SETH is claimed to fall too. OpenAI's manuscript lists ETH, SETH, Gap-ETH, NSETH and #ETH as refuted. Anthropic's paper states ETH, SETH, NSETH and #ETH are false.
Timeline
- 1999: Impagliazzo and Paturi define sk and ETH.
- 2026-10-16: Anthropic's paper says an internal Claude model found its core algorithm on this date. This is self-reported.
- 2026-10-17: Original date on OpenAI's manuscript, later revised on October 25. This is a document date, not a discovery date, so it does not show who was first.
- 2026-10-26: OpenAI adds the manuscript and Lean work at 20:52 UTC. Impagliazzo, Paturi and Williams publish their letter. Kintali's simplified exposition carries this date.
- 2026-10-27: Anthropic adds its paper and Lean work at 03:07 UTC. The paper itself is dated October 26.
- 2026-10-28: Fortnow posts his summary. Toledo comments on replaying both developments.
- 2026-10-29: Francis Zane collects expositions by Sellke, O'Donnell and Kintali.
- 2026-10-30: Zane opens a Lean replication thread.
- 2026-10-31: Busnello posts replication receipts for both proofs.
Numbers that differ
Reports disagree because the repository changed and sources count different things. OpenAI's catalogue listed 722 manuscripts in 372 families on October 6, and 721 in 373 from October 26. Family numbers run past the family count because some are unused, which is why ETH is number 378. Mark Sellke's slides, and he works at OpenAI, define ρ(n) with one log log n factor, while OpenAI's manuscript defines ρ(n) with a squared factor. Anthropic's ETH paper reports 14 million output tokens and the 3SUM paper reports 16 million. Those are separate sessions.
Source: the linked papers, repositories and posts, checked on November 1, 2026.
Evidence boundary: We read these sources and compared the bounds against them. We did not run Lean, did not review the mathematics, and could not open OpenAI's announcement page, which refused our requests. Finding no peer-reviewed publication reflects the searches we ran, not every journal and proceedings. Anthropic is a party to this event and also makes the model that helped draft this site. See the method.