OpenAI claims its model refuted the Exponential Time Hypothesis, verified in Lean
AIFlow_ML · x · 2026-10-27
MIT complexity theorist Ryan Williams announced that an internal OpenAI model has produced a claimed refutation of the Exponential Time Hypothesis (ETH), with Impagliazzo, Paturi and himself asked to organize independent review. Dan Roberts announced "three new discoveries" in math, CS and physics; the CS headline result — a deterministic algorithm exactly counting satisfying assignments of k-CNF formulas in (n+m)^{O(k)}2^{n/(log n)^{1/3+o(1)}} time — is claimed to be verified in Lean. A major, contested claim against a load-bearing complexity conjecture.
More from Models
- Reasoning is signed: building a universal LLM gateway hits encrypted CoT walls — respan-81 · 2026-10-27
- Gemini 4 Argon reportedly beats GPT-6 Astra on a new CS research benchmark — Saboo_Shubham_ · 2026-10-27
- LlamaIndex releases OCRia-1, a 4B document parsing VLM topping ParseBench at 87.4 — llama_index · 2026-10-27
- Baidu open-sources Unlimited OCR 2: near-constant latency on documents of any length — Baidu_Inc · 2026-10-27
- Gary Marcus walks back: his earlier take on OpenAI's latest result was 'too generous' — GaryMarcus · 2026-10-27
- UC Berkeley paper: RL reweights LLM reasoning strategies rather than expanding them — burny_tech · 2026-10-27