"The Exponential Time Hypothesis is false": major complexity claim spreads
davidad · x · 2026-10-27
Andrew Curran posted on X claiming that the Exponential Time Hypothesis (ETH) is false, linking a paper, with davidad amplifying it. ETH asserts no subexponential algorithms exist for problems like 3-SAT and underpins many hardness results in complexity theory. If the claim holds up, it would shake a large body of lower-bound proofs — a major development, pending community verification.
More from Research
- General Physics Transformer shows foundation-model paradigm works for physics simulation — burny_tech · 2026-10-27
- Kimi Team proposes Attention Residuals, replacing fixed residual accumulation with learned attention — burny_tech · 2026-10-27
- Early reproduction of Kimi's Attention Residuals in a physics transformer shows faster convergence — burny_tech · 2026-10-27
- AtomGPT launches Ductility Explorer to screen JARVIS-DFT for hard-ductile materials — CatAstro_Piyush · 2026-10-27
- ETH reviewers say OpenAI's claimed disproof shouldn't be read as certified — fortnow · 2026-10-27
- OpenAI claims Exponential Time Hypothesis is false, solving 3SAT in subexponential time — fortnow · 2026-10-27