Limits and Constants of OpenAI's Claimed ETH Refutation
cs.CC, cs.DS, math.CO
Submitted: 2026-10-31
Updated: 2026-10-31
License: http://creativecommons.org/licenses/by-sa/4.0/
The gist: A recent OpenAI preprint claims a deterministic algorithm that counts the satisfying assignments of a k-CNF formula in time 2 O k(n n/sqrt n), and 2 O(n/sqrt n) at bounded clause density…
Terminology
Abstract
A recent OpenAI preprint claims a deterministic algorithm that counts the satisfying assignments of a k-CNF formula in time 2 O k(n n/sqrt n), and 2 O(n/sqrt n) at bounded clause density, which would refute the Exponential Time Hypothesis. The headline bound is proved by tensor contraction; the body develops an interpolation algorithm with the weaker exponent n(n) 2/sqrt n. This note does four things. First, it explains the interpolation algorithm in plain terms. Second, it asks how large n must be for the bounds to bite. The preprint states no constants, so we treat the hidden constant C as a parameter: the general bound beats the 2 n of brute force only beyond n about 10 32 for C=2, 10 126 for C=3 and 10 3517 for C=10. We then extract the constants from the tensor-contraction proof: for every input with m clauses at bounded density, the running time it certifies stays above 2 n unless 2(n+m)>10 9, and on random 3-CNF at the satisfiability threshold unless 2 n>5 times10 11. So the bounds are subexponential as n to infinity, but the proof certifies no speed-up over brute force for any input of bounded density that could ever be written down. Third, for the clause-product form of the interpolation algorithm we prove limits in a cost model matching the preprint's evaluation. By a short algebraic lemma, polynomial cost needs components of O(cubed n) variables with per-point evaluation, or primal treewidth O(squared n) with dynamic programming over the groups. So the scheme costs 2 Ω(sqrt tw) at treewidth tw, 2 Ω(sqrt n) with high probability on random 3-CNF above clause density 3, and 2 Ω(n 1/3) even on trivially countable path formulas. We explain why the preprint's sharper routes escape these limits. Fourth, we report experiments.
Sources
- The Quasi-Polynomial Low-Degree Conjecture is False
- Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?