Complexity researcher on the ETH refutation: stronger than P≠NP but practically moot
burny_tech · x · 2026-10-27
Responding to OpenAI's claimed refutation of the Exponential Time Hypothesis, bzogrammer offers a technical breakdown: ETH is a much stronger statement than P≠NP, so its falsity is surprising but breaks little. The new bounds are technically sub-exponential — roughly 2^n divided by a complicated log-sqrt expression — still close to exponential. Given SAT solvers have worked extremely well in practice for decades (with proven <O(2^n) solvers long known), slightly tighter bounds aren't shocking. The upshot: for any O(k^n) there's an algorithm beating any fixed k at absurdly large n — a cute result, but we already knew NP problems are easier in practice than in theory. The original announcement notes the result was verified in Lean.
More from Research
- Map of secure program synthesis: ruby-lean in Lean and the race to formally verify everything — burny_tech · 2026-10-27
- OpenAI claims rigorous Yang-Mills existence proof; physicist Woit calls the announcement misleadingly vague — burny_tech · 2026-10-27
- Researcher corrects 'Uncheatable forecast': admits flop-uncontrolled compute estimate — dlwh · 2026-10-27
- Buzz grows over claimed subexponential 3SAT and what it would mean for NP problems — burny_tech · 2026-10-27
- OpenAI internal model claims to refute ETH; Impagliazzo, Paturi and Williams to organize independent review — aminkarbasi · 2026-10-27
- D3-Gym: first auto-constructed verifiable environments for data-driven scientific discovery, shown at EMNLP 2026 — hhsun1 · 2026-10-27