OpenAI's claimed refutation of ETH: exhaustive search below 2^131071

On 26 October 2026, OpenAI announced that its model had refuted the Exponential Time Hypothesis (ETH) with a deterministic algorithm that counts the satisfying assignments of a k-CNF in subexponential time. This note does not judge the correctness of the proof. It computes, from the paper's own parameter choices and tests, the input size at which the algorithm stops being an exhaustive search, a number the paper does not state. The algorithm of the main text is an exhaustive search on every input with fewer than 2^(10^10) variables, and the algorithm in its Appendix D, which attains the bound of the main theorem, on every input with fewer than 2^131071 variables and clauses. If the result holds, the hypothesis of every lower bound conditioned on ETH or SETH is false, while on every input that fits in memory of any computer the algorithm is an exhaustive search. The note also checks the Lean statement that OpenAI reports as verified. It is a correct statement of the intended result, for a weaker but still subexponential bound. Files: the note as a PDF and a Python script, eth_thresholds.py, that reproduces the thresholds in exact integer arithmetic (Python 3.10 or later, no dependencies).Addendum: On 27 October 2026, the day this note appeared, Anthropic posted an independent refutation of ETH on the Hexagon preprint server ("A 2^o(n) Time Algorithm for 3-SAT", hexagon:2610.00577v1), with a different algorithm and a Lean 4 proof that Anthropic reports as checked by Lean's kernel and by the independent kernel nanoda. That paper states its own thresholds: for 3-CNF formulas with m = 5n clauses, the bound it proves does not improve on 2^n unless n > 10^10000, and its bound in n alone does not unless n > 10^(10^8). Evaluating the paper's level recurrence numerically, rather than through its lower bound on the exponents, raises these necessary sizes to 2^275616 clauses and 2^(1.7·10^10) variables. Below 2^162 clauses and 2^306 variables, the paper's algorithms try all assignments by explicit instruction, and the true cutoffs may be larger, since the paper leaves a constant of its construction unspecified.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-27
DOI
https://doi.org/10.5281/zenodo.23688831
Primary Topic
Complexity and Algorithms in Graphs
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

OpenAI's claimed refutation of ETH: exhaustive search below 2^131071

Stefan Szeider
4 links
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
article

OpenAI's claimed refutation of ETH: exhaustive search below 2^131071

Stefan Szeider
article en

Abstract

On 26 October 2026, OpenAI announced that its model had refuted the Exponential Time Hypothesis (ETH) with a deterministic algorithm that counts the satisfying assignments of a k-CNF in subexponential time. This note does not judge the correctness of the proof. It computes, from the paper's own parameter choices and tests, the input size at which the algorithm stops being an exhaustive search, a number the paper does not state. The algorithm of the main text is an exhaustive search on every input with fewer than 2^(10^10) variables, and the algorithm in its Appendix D, which attains the bound of the main theorem, on every input with fewer than 2^131071 variables and clauses. If the result holds, the hypothesis of every lower bound conditioned on ETH or SETH is false, while on every input that fits in memory of any computer the algorithm is an exhaustive search. The note also checks the Lean statement that OpenAI reports as verified. It is a correct statement of the intended result, for a weaker but still subexponential bound. Files: the note as a PDF and a Python script, eth_thresholds.py, that reproduces the thresholds in exact integer arithmetic (Python 3.10 or later, no dependencies).Addendum: On 27 October 2026, the day this note appeared, Anthropic posted an independent refutation of ETH on the Hexagon preprint server ("A 2^o(n) Time Algorithm for 3-SAT", hexagon:2610.00577v1), with a different algorithm and a Lean 4 proof that Anthropic reports as checked by Lean's kernel and by the independent kernel nanoda. That paper states its own thresholds: for 3-CNF formulas with m = 5n clauses, the bound it proves does not improve on 2^n unless n > 10^10000, and its bound in n alone does not unless n > 10^(10^8). Evaluating the paper's level recurrence numerically, rather than through its lower bound on the exponents, raises these necessary sizes to 2^275616 clauses and 2^(1.7·10^10) variables. Below 2^162 clauses and 2^306 variables, the paper's algorithms try all assignments by explicit instruction, and the true cutoffs may be larger, since the paper leaves a constant of its construction unspecified.

Zenodo (CERN European Organization for Nuclear Research)
TU Wien (AT)
Openalex Percentile: Top 14%
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
OpenAI's claimed refutation of ETH: exhaustive search below 2^131071 — Stefan Szeider · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS