OpenAI paper claims to refute Exponential Time Hypothesis with subexponential 3-SAT algorithm

burny_tech · x · 2026-10-29

OpenAI released a paper claiming to refute the Exponential Time Hypothesis (ETH), which posits 3-SAT needs 2^{Ω(n)} worst-case time.

Result: a deterministic algorithm that exactly counts satisfying assignments of any k-CNF, running in (n+m)^{Ok(1)}·2^{n/(log n)^{1/2+o(1)}} time with polynomial space for every fixed k≥2.
Since a count of zero decides satisfiability, this directly refutes ETH — an asymptotic worst-case proof, not measured runtimes.
Technique: reorganizing exact counting so it's recoverable from smaller group-by-group sums, via shared linear summaries, low-degree replacement forms, and counting common zeros of sparse polynomial equations (64 pages with appendices).
If it holds, results built on ETH/SETH across complexity theory would be shaken; academic scrutiny pending.

More from Research