Two Minute Papers · 2026-10-30 · notable
Two Minute Papers — 'OpenAI Claims It Just Did The Impossible'
Two Minute Papers covers OpenAI's AI-written manuscript 'The Exponential Time Hypothesis is False', which claims a subexponential algorithm for counting solutions of fixed-width CNF formulas.
Károly Zsolnai-Fehér looks at OpenAI's claim that its model refuted the Exponential Time Hypothesis.
What is it?
'OpenAI Claims It Just Did The Impossible' went up on Two Minute Papers on 30 October 2026. The video description links the paper 'The Exponential Time Hypothesis is False' in OpenAI's openai/math repository.
How does it work?
According to the openai/math history page, the manuscript gives a deterministic algorithm that exactly counts satisfying assignments of fixed-width CNF formulas in subexponential time and polynomial space. Its 3-SAT case is what would refute the hypothesis.
Why does it matter?
The Exponential Time Hypothesis sits under many hardness results in computer science. An independent group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams is examining the proof, so the claim is still unconfirmed.
Who is it for?
anyone following AI in mathematics