Community Reacts to Apparent Refutation of the Exponential Time Hypothesis
Around October 27, a major theoretical result spread rapidly through the complexity theory community: k-SAT can be solved in 2^(n/log n) time, meaning the Exponential Time Hypothesis (ETH) does not hold. The claim traces back to Scott Armstrong's announcement that "ETH is false," which was amplified by mcarbin and others asserting "ETH has been proven false," flooding a Q&A thread on MIT CSAIL. Developer Eric Zhang (ekzhang1) tweeted that he was stunned, saying that SAT requiring exponential time is common sense taught in the very first CS class, and he had never questioned it.
Confirmed
- The circulating result: k-SAT has a 2^(n/log n) time algorithm, falsifying ETH; this bound is technically subexponential.
- bzogrammer offered a technical read: ETH is a stronger claim than P≠NP, so its falsification is surprising but doesn't overturn that many existing results.
- Debate within the field: some call it one of the biggest theoretical results ever, but verbine and others counter that it isn't surprising, that k-SAT itself was never a big deal, and that another result released October 6 is more significant than ETH being falsified.
Unconfirmed
- The correctness of the proof itself and its formal publication status are not confirmed in the thread materials; most of the discussion is community relay and commentary.
Why it matters
- ETH is a lower-bound assumption treated as textbook common sense, and its collapse breaks long-held intuition.
- @rebelcrayon noted the breakthrough resembles the earlier O(n log n) multiplication algorithm but with more serious consequences: multiplication could at most save a log n factor, whereas with ETH broken "there's a lot of room downstream," and some security assumptions may need a full re-examination.
2026-10-27 ~ 2026-10-27 · 5 related posts
- Episode 1: OpenAI Claims Three Major AI-Generated Scientific Discoveries, Including a Refutation of ETH(2026-10-27, 69 posts)
- Episode 2: Brockman on AI math hype: P probably still doesn't equal NP(2026-10-27, 6 posts)
- Episode 3: Community Reacts to Apparent Refutation of the Exponential Time Hypothesis(2026-10-27, 5 posts)
- Episode 4: Anthropic says internal Claude model autonomously discovered sub-exponential 3-SAT algorithm refuting ETH(2026-10-27, 8 posts)
- Episode 5: AI Claimed Solution to ETH Problem Faces Verification Doubts(2026-10-27, 2 posts)
Primary sources
- Complexity researcher on the ETH refutation: stronger than P≠NP but practically moot — burny_tech · 2026-10-27
- CS theorists debate: October 6 results, incl. Unique Games Conjecture, dwarf the ETH refutation — burny_tech · 2026-10-27
- "ETH Proved False" Claim Spreads as Researchers Quote-Tweet MIT CSAIL — burny_tech · 2026-10-27
- "ETH is false": CS community buzzing over claim that upends SAT exponential-time assumption — akbirthko · 2026-10-27
- [source] Conjectured lower bound reportedly broken, ETH-based security assumptions may need revisiting — IgorCarron · 2026-10-27