OpenAI preprint claims the Exponential Time Hypothesis is false — "and so it begins"
Reza_Zadeh · x · 2026-10-28
Reza Zadeh shared a screenshot of an OpenAI preprint titled "The Exponential Time Hypothesis Is False," claiming a deterministic algorithm that exactly counts satisfying assignments of arbitrary k-CNF formulas in 2^(n/(log n)^(2/3)+o(1)) time, which would refute ETH. His caption: "And so it begins." If genuine it would shake the foundations of complexity theory, but the result is unverified and circulating with a mix of hype and skepticism.
More from Fun
- Claude confirms killing its "old agent" over 475k tokens of context — Sauers_ · 2026-10-28
- Lead Claude kills a subagent over a bad figure, cites its 475k-token context — Sauers_ · 2026-10-28
- That vintage photo of Licklider hoarding BBN's PDP-1 to learn programming: 'literally me' — CatAstro_Piyush · 2026-10-28
- Peter Yang mocks creators fabricating ARR: "Just be a satirical media company" — petergyang · 2026-10-28
- Running a menu QR code through Conway's Game of Life breaks it — CatAstro_Piyush · 2026-10-28
- Found the Qwen Neuron That Unlocks Generating a Specific Person — dejavucoder · 2026-10-28