OpenAI claims Lean proof refuting the exponential-time hypothesis
fortnow · x · 2026-10-29
Lance Fortnow blogs on the week's big news: OpenAI announced a Lean-formalized proof that the exponential-time hypothesis (ETH) is false, with Anthropic releasing its own paper and Ryan O'Donnell and Shiva Kintali posting follow-up proofs favoring simplicity. OpenAI will partner with complexity theorists Russell Impagliazzo, Mohan Paturi and Ryan Williams to verify it.
ETH (Impagliazzo–Paturi 1999) asserts 3-SAT requires 2^{cn} time. The OpenAI algorithm decides satisfiability (and counts solutions) for k-CNF formulas in (n+m)^{O(1)}·2^{O(n log log n / sqrt(log n))} time, refuting ETH and hence SETH. Fortnow recommends starting with O'Donnell's paper to understand the proof.
Related event: OpenAI Model Claims ETH Is False, Verified in Lean(4 posts)→
More from Research
- H-Net learns dynamic tokenization for code, showing 3-5x efficiency gains — gharik · 2026-10-29
- BlackboxNLP kicks off at EMNLP2026 Budapest, opening keynote on how LLMs read — gsarti_ · 2026-10-29
- QUAN paper: real-valued quaternion convolution nets SOTA in oriented detection — Bryce Grant · 2026-10-29
- Tim Vieira Explains Conditional Poisson Sampling with Verified Identities and Interactive Visuals — xtimv · 2026-10-29
- Reward-model ensembles from different pretraining seeds resist reward hacking better — vxnuaj · 2026-10-29
- Google DeepMind engineer shows five CUDA optimizations that speed up 3D Gaussian Splatting by 10.5x — janusch_patas · 2026-10-29