The Exponential Time Hypothesis

The Exponential Time Hypothesis (ETH) of Impagliazzo and Paturi postulates that deciding satisfiability of 3-CNF formulas on n variables requires time 2^Ω(n) in the worst case. A manuscript dated 25 October 2026 in OpenAI's public mathematics collection (github.com/openai/math), added on 26 October 2026, claims a deterministic algorithm that counts the satisfying assignments of any k-CNF in subexponential time and polynomial space for every fixed k, and so claims to refute ETH. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper or a formal proof is not presented here as independent verification.

Background

As recounted in the related-work section of the manuscript:
- Schöning's local search decides k-SAT in randomized time (2 − 2/k)ⁿ up to polynomial factors, and PPSZ and its later analyses by Hertli, by Hansen, Kaplan, Zamir and Zwick, and by Scheder give the best known randomized bounds; for 3-SAT the manuscript cites a preprint of Jiang and Cai with a randomized bound of about 1.307ⁿ and Liu's deterministic bound of about 1.328ⁿ.
- ETH asserts that 3-SAT, and hence k-SAT for every fixed k ≥ 3, requires deterministic time 2^Ω(n); the Strong Exponential Time Hypothesis (SETH) asserts that for every ε in (0, 1) some fixed k has no 2^(1−ε)n-time algorithm. Gap-ETH and the nondeterministic variant NSETH are further strengthenings. These hypotheses underlie many conditional lower bounds in parameterized and fine-grained complexity.
- In 2016 R. Williams refuted the Merlin–Arthur version of SETH by a protocol certifying k-CNF unsatisfiability in time 2^n/2 up to polynomial factors.

The original result

Claim. Theorem 1.1 of The Exponential Time Hypothesis is False states that for each fixed k ≥ 2 a deterministic algorithm computes the number of satisfying assignments of a k-CNF with n ≥ 20 variables and m clauses using (n + m)^O_k(1) bits of space and (n + m)^O_k(1) 2^{O_k(n log log n/√log n)} bit operations, improving to 2^{O_k,D(n/√log n)} when m ≤ Dn. The abstract summarizes the time bound as (n + m)^O_k(1) 2^{n/(log n)^1/2+o(1)}.
Consequences stated in the manuscript. The manuscript states that the theorem refutes ETH, SETH, Gap-ETH and NSETH, and the bounded-error randomized versions of ETH, SETH and Gap-ETH; that it does not conflict with unconditional exponential lower bounds for restricted proof systems such as regular resolution; and that conditional lower bounds based on SETH lose that basis, although some of them also follow from weaker hypotheses such as the Orthogonal Vectors Conjecture. Further corollaries: subexponential-time approximation of Max-k-SAT to within εm clauses of the optimum; through Williams's theorem that a refutation of ETH implies that E^NP lacks linear-size circuits, a language in E^NP whose circuit size exceeds cn√log n for infinitely many n; and subexponential algorithms for inverting Boolean maps with constant output locality. The manuscript states that the circuit consequence is not a superpolynomial circuit lower bound for NP.
Method, as described in the technique overview: for formulas in which each variable occurs a bounded number of times, the count is expressed through a polynomial family with easier evaluation points; the sum is separated by fixing a set of linear measurements, the count is recovered from Taylor coefficients, and low-degree replacement linear forms control the cost. The general case uses a counting algorithm for common zeros of sparse low-degree polynomial systems over F₂.
Verification announced by the collection. The collection's release notes of 26 October 2026 state that an independent working group of computer scientists led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will examine and explain the proof, and that the materials were made public immediately at the group's request.
Source. The manuscript The Exponential Time Hypothesis is False at commit 7ef5c0c; release notes in history.md under 26 October 2026.
Formalization, as described by the repository. The scope note lean/docs/378.md states that Lean proves, for fixed k ≥ 2, that a deterministic machine exactly counts the satisfying assignments of a canonically encoded k-CNF on n variables in time (L + 1)^O_k(1) 2^{O_k(n(log log n)²/√log n)}, where L is the bit length of the encoding, while visiting at most (L + 1)^O_k(1) tape cells; the manuscript's sharper time bound is stated separately and is outside this statement. The comparator statement is SubexponentialSAT.lean.

Public follow-up work

Date	Work	Relation	Public claim	Public status (checked 27 October 2026)
2026-10-27	Claude, Anthropic, A 2^o(n) Time Algorithm for 3-SAT, Hexagon 2610.00577v1, with a Lean 4 formalization in anthropics/formal-math, folder eth	Parallel (independent claim)	Claims a deterministic algorithm that counts the satisfying assignments of a 3-CNF on n variables in time 2 to the power O of n log log n divided by the square root of log n, and so refutes ETH. The provenance statement says that the core algorithm was found on 16 October 2026 by an internal Claude research model and that the work is independent of and concurrent with OpenAI's.	Hexagon record, version 1 of 27 October 2026, labelled as primarily AI-generated text. The repository README states that the Lean statements of the refutation and of the main theorem depend only on Lean's three standard axioms, and describes a Comparator check with a second kernel run by the repository's continuous integration. Not refereed.
2026-10-26	R. O'Donnell, Some exposition of "The Exponential Time Hypothesis Is False" (PDF, 12 pages)	Reading (exposition)	Specializes Sections 2–4 of the manuscript to counting the independent sets of a 3-regular graph with loose parameters. It gives a Las Vegas randomized algorithm in expected time v^O(1) 2^{O(v/(log v)^1/4)} with polynomial space. It states that the randomness can be removed as in Section 4.4 of the manuscript and that, by a lower bound of Liu and Chen for counting vertex covers under #ETH, a deterministic subexponential counter refutes ETH. The key step is an approximation of parity on Hamming-weight layers applied to commuting SWAP operators.	PDF on the author's university web page, dated 26 October 2026. A footnote states that it was produced through interaction with LLMs.
2026-10-27	AI Proved What?, episode 378 The Exponential Time Hypothesis is false?	Reading (exposition)	Video explainer of the claim that for every fixed clause width k a deterministic polynomial-space algorithm counts the satisfying assignments of a k-CNF with n variables in time polynomial in the input size times 2 to the power C·n log log n divided by the square root of log n, with C depending on k. The episode states that neither P = NP nor faster algorithms for every NP problem are claimed, and that by the site's own computation the explicit parameters of the technique overview take effect only for inputs with more than three billion digits.	Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 26 October 2026: posted as a preprint: OpenAI, 67 pages, dated October 17, revised October 25, 2026, added to the repository October 26; under expert review: per OpenAI, an independent working group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will examine and explain the proof; peer reviewed: not yet; formalized in Lean: a weaker bound, with exponent n times the square of log log n divided by the square root of log n, which the site has not run.
2026-10-27	The Exponential Time Hypothesis, and OpenAI's claim that it is false, an interactive explainer with source repository gravitypersists/explainer-eth-disproved	Reading (exposition)	Explains for readers new to complexity theory what ETH says, why it mattered, what rests on it and what would follow if the claimed refutation holds. It presents the result as a claim pending review.	Web page; the repository README states that it was written by Claude Opus 5.5 with the didactician skill. Read on 27 October 2026.
2026-10-27	M. Subbarao, Ram Calculus and the Exponential Time Hypothesis: Exact Finite-Algebra Reformulations, Aggregated Boolean Jets, and Precision-Certified Counting, revision 4, technical report in the repository muralisubbarao2/OpenAI-paper-Oct26-ExponentialTimeHypothesis, with a summary report	Reading (technical report)	Rederives the manuscript's algebraic architecture and states local refinements: an aggregated Boolean-jet identity that replaces the restricted-count calls indexed by pairs of sets by calls indexed by single sets over a larger coefficient algebra, target-specific two-adic precision certificates, and exact tests and timings on small finite layouts. The report states that it establishes neither a stronger general SAT exponent nor an independent refutation of ETH, and that the manuscript's full algorithm and its Lean dependency closure were not executed.	Technical report dated 27 October 2026, with a summary report dated 26 October 2026; the report states that it was prepared with the assistance of AI models. Not refereed.
2026-10-27	S. Schlesinger, A. Kovsharov, E. Demaine, C. Reitwiessner and contributing AI workers, a native port into the Lean library cslib-community/complexitylib, formal abstract OpenAI: the Exponential Time Hypothesis is false, with a PDF rendering	Use (Lean port)	Ports the interpolation-scale route of Sections 3–6 and Proposition 6.4 of the manuscript onto the library's own multi-tape Turing machines and complexity classes. The abstract states four theorems: for each fixed clause width k, one deterministic machine computes the exact number of satisfying assignments of every formula of width k in time 2 to the power of a constant times n times the square of log log n divided by the square root of log n, multiplied by a polynomial in the encoding length, and in polynomial work space; ETH is false; SETH is false; and every fixed-width SAT exponent is zero. It states that the sharper bound of Theorem 1.1 and Appendix D is not formalized.	Merged into the main branch on 27 October 2026 as pull request 1338, which closed the port issue 1226. The pull request states that Codex and Claude Code workers wrote the abstract and adaptation and that a separate reviewer worker reviewed it. The abstract notes that Lean checks the proofs, while its audit command checks only the dependency boundary of the definitions and statements, not their English reading. Read on 28 October 2026.
2026-10-27	Trust, but Replay, replay audit note OpenAI ETH-disproof formalization in the repository chokmah-me/fragile-proof-audit	Verification (Lean rebuild and statement audit)	Rebuilds the collection's Lean formalization at the October release with Lean 4.34.1 and reports that the 3,977-file solution module builds with no sorry and no unsafe or native-code escape, and that the theorem exact_count_and_sat depends only on propext, Classical.choice and Quot.sound. Because the solution module carries its own copies of the statement's definitions, it prints the 36 statement components in two separate environments, one importing only the challenge and one importing only the solution, and finds the two outputs identical. It audits the Lean statement only, not the manuscript, and did not run the repository's own Comparator tool. A companion note applies the same checks to the Lean formalization of the independent Anthropic claim listed above.	Audit closed with verdict PASS on 27 October 2026, with the GitHub Actions run recorded in the note. The note states that it was produced by the AI agent Muse Spark 1.3 of Meta and that the shepherds' review of the manuscript is a separate process. Read on 28 October 2026.
2026-10-26	S. Kintali, A simplified proof of ETH is false, PDF, 22 pages	Reading (exposition with simplified proofs)	Presents, as a simplified exposition of the manuscript's proof, a deterministic algorithm that for every fixed ε > 0 decides 3-SAT on n variables and m clauses with C_ε (n + m + 1)^c_ε 2^εn bit operations, combining sparsification, bounded occurrences, spectral replacement and rational interpolation. It aims only at the basic statement of ETH and does not optimize logarithmic factors: for 3-CNFs in which each variable occurs at most three times it counts satisfying assignments with one integer parameter s, taking r = s, Q = s⁴, R = s³ and τ = s⁻⁶. It states that this counting step is proved without the manuscript's new lemmas and that the only result on SAT complexity used without proof is the sparsification lemma of Impagliazzo, Paturi and Zane.	PDF on the author's web page, dated 26 October 2026. It states that the author prompted Claude and ChatGPT interactively to simplify the proofs, then expanded the proofs by hand, made them more readable and added explanations and a worked example. Not refereed. Read on 28 October 2026.
2026-10-27	Verification record unaltuzun/exponential-time-hypothesis-verify of Ü. Tüzün, with the report ETH / Subexponential SAT — Mathematical Reconstruction and Verification Audit	Verification (partial: static audit and small-instance reproduction)	Reports a static audit of the 3,091-module import closure of the Lean proof, with no sorry, axiom, native_decide or unsafe declaration, and finds the definitions of the challenge file textually identical to those of the library. It reimplements the core mechanism of Sections 2 and 4.2 from the manuscript, not from Lean, in exact rational arithmetic and checks its identities on small random formulas. It states that Lean formalizes the weaker exponent n times the square of log log n divided by the square root of log n, not the bound of Theorem 1.1, and that it did not verify the asymptotic bookkeeping or the tensor-contraction sharpening.	Repository created 27 October 2026. The report states that the Lean build, the kernel check, #print axioms and the Comparator were not achieved, because the Mathlib cache was unreachable from its sandbox. The README states that the work was carried out with substantial AI assistance from Claude of Anthropic and is not an endorsement; the report names Anthropic's parallel claim as a conflict of interest. Read on 28 October 2026.
2026-10-27 (version 2)	X. Chen, Exact Algorithms and Complexity of the Smallest Grammar Problem (arXiv:2610.32298, v2)	Use (application of the tensor contraction theorem)	For a string of length n over at most σ symbols, with R = log_σ n, gives a deterministic exact algorithm for the smallest grammar problem in polynomial space and time n^O(1) 2^{O(n log log n / (R √log n))}, by combining disjoint representative occurrences and a sparse interval certificate with the Boolean tensor contraction theorem of the manuscript. Independently of that theorem it gives exact algorithms in time 1.872258ⁿ up to polynomial factors and in linear space, and it states unconditional quantitative transfers from smallest-grammar algorithms to sparse SAT algorithms.	arXiv preprint, version 2 of 27 October 2026; version 1 was posted on 23 October 2026. The paper states that GPT-6 Pro produced the binary-alphabet NP-completeness proof and the tunable-alphabet reductions, and that the sparse-interval tensor algorithm was developed through discussions with GPT-5.6 Pro and GPT-6 Pro. Read on 28 October 2026.

Notes

The background summarizes the manuscript's own account of earlier work.
Within the collection, the manuscript Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalence states time exclusions conditional on forms of the Exponential Time Hypothesis, while its companion Unconditional time lower bounds for Weisfeiler–Leman equivalence states an unconditional bound; see The computational complexity of Weisfeiler–Leman refinement.
The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.