Limits and Constants of OpenAI's Claimed ETH Refutation
Abstract
A recent OpenAI preprint claims a deterministic algorithm that counts the satisfying assignments of a k-CNF formula in time 2Ok(nloglog n/√(log n)), and 2O(n/√(log 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(loglog n)2/√(log 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 2n of brute force only beyond n≈ 1032 for C=2, 10126 for C=3 and 103517 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 2n unless log2(n+m)>109, and on random 3-CNF at the satisfiability threshold unless log2 n>5×1011. So the bounds are subexponential as n→∞, 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(log3 n) variables with per-point evaluation, or primal treewidth O(log2 n) with dynamic programming over the groups. So the scheme costs 2Ω(√(tw)) at treewidth tw, 2Ω(√n) with high probability on random 3-CNF above clause density 3, and 2Ω(n1/3) even on trivially countable path formulas. We explain why the preprint's sharper routes escape these limits. Fourth, we report experiments.
Related
- From Hermite Chaos to an Attractive Log-Gas: Explicit High-Rank Limits of Iterated-Logarithm and Tail Constants
- Refutation of the Non-Cancelling Intersections Conjecture
- The Sandier-Serfaty triangular-lattice conjecture: an independent reproduction of a claimed finite certificate, an adversarial audit of the claimed reduction, and a Lean statement (no proof of the conjecture is claimed)
- The Deligne--Drinfeld conjecture after OpenAI
- A Note on the OpenAI Construction of Counterexamples to the Kaplansky Direct-Finiteness Conjecture
BibTeX
@misc{dias2026limits,
title = {{Limits and Constants of OpenAI's Claimed ETH Refutation}},
author = {Fabio Dias and Yvens Lima},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00517},
eprint = {2611.00517},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00517},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Limits and Constants of OpenAI's Claimed ETH Refutation
AU - Fabio Dias
AU - Yvens Lima
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00517
UR - https://arxiv.org/abs/2611.00517
AB - A recent OpenAI preprint claims a deterministic algorithm that counts the satisfying assignments of a k-CNF formula in time 2^O_k(nloglog n/√(log n)), and 2^O(n/√(log 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(loglog n)^2/√(log 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≈ 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 log_2(n+m)>10^9, and on random 3-CNF at the satisfiability threshold unless log_2 n>5×10^11. So the bounds are subexponential as n→∞, 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(log^3 n) variables with per-point evaluation, or primal treewidth O(log^2 n) with dynamic programming over the groups. So the scheme costs 2^Ω(√(tw)) at treewidth tw, 2^Ω(√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.
ER -