OpenAI's ETH-refutation claim: SAT bounds, Lean scope and what remains unconfirmed

What the Exponential Time Hypothesis says

For a 3-SAT formula, the question is whether there is an assignment of its variables that makes every clause true. The Exponential Time Hypothesis, or ETH, predicts exponential worst-case difficulty measured in the number of variables. Many conditional hardness results use that assumption to explain why particular fast algorithms may not exist.

Exact counting asks for the number of satisfying assignments. It also answers the decision problem: the formula is satisfiable precisely when that count is positive. A correct subexponential exact-counting algorithm for 3-SAT would therefore refute ETH.

The exact claim and the three runtime statements

OpenAI's manuscript dated 17 October and revised 25 October claims a deterministic algorithm for exact counting on fixed-width k-CNF formulas, for each fixed k ≥ 2, using polynomial space. Its Theorem 1.1 states bounds for n ≥ 20.

• Documented Lean scope: (L+1)^O_k(1) × 2^{O_k(n(log log n)²/√log n)}, where L is canonical input bit length.
• Revised manuscript, m clauses: (n+m)^O_k(1) × 2^{O_k(n log log n/√log n)}.
• Revised manuscript, fixed density m ≤ Dn: (n+m)^O_k,D(1) × 2^{O_k,D(n/√log n)}, for fixed D.

These bounds are not interchangeable. The manuscript's sharper exponents must not be described as covered by the documented Lean theorem.

What the formal artifacts establish about scope

Scope 378 explicitly separates the released formal bound from the revised paper. It documents polynomially many visited tape cells at every execution prefix; the challenge uses log(n+16) to handle small inputs.

The SubexponentialSAT target and configuration expose statements and mappings for examination. Kingy did not rebuild them, run the algorithm, complete a semantic proof audit or independently reproduce a formal check.

Significance without overstating the consequences

For fixed k, the stated exponential factors are subexponential in n. If the argument is correct, the k = 3 case would overturn ETH and require reassessing conclusions that depend on it. That would be a major theoretical change, even without a practical implementation.

The displayed bounds are superpolynomial upper bounds, not a proof that a polynomial algorithm is impossible. This does not settle P versus NP, benchmark a practical speedup or demonstrate that deployed cryptography is broken. The paper also warns that arbitrary polynomial-size reductions need not preserve the parameters required to transfer a subexponential runtime.

AI attribution and the outside examination

OpenAI reports natural-language model output on 16 October and formalization on 17 October, followed by public release on 26 October. It gives no model version or full allocation of human and AI formalization work. The manuscript's displayed credit is OpenAI.

The announced external group is led by Russell Impagliazzo and Ramamohan Paturi at UC San Diego and Ryan Williams at MIT. Their examination role does not make them manuscript authors or establish their endorsement. No completed independent correctness verdict was located in the bounded 26 October check. The record remains provisional and unrefereed.

Revision history and the next evidence to look for

The paper's original date is 17 October; its revised version is dated 25 October. The record was added on 26 October with the manuscript/formal-scope distinction already explicit. This explanation preserves that scientific history and does not silently promote the claim.

A completed specialist report, correction, independently reproduced formal target or journal decision would each add a different kind of evidence. Compare the separate local-smoothing claim and the tracker's evidence standards. Similar release dates and public Lean materials do not give the two results a shared correctness verdict.