What happened
On 26 October, OpenAI and Anthropic reported AI-generated proofs that overturn a long-held belief about how hard some problems are to solve. The result concerns the Exponential Time Hypothesis, or ETH. 1 2
Anthropic says its model found the core algorithm without human input. Researchers then helped improve the paper. AI had produced an answer to a problem that had occupied computer scientists for decades. 2
Why this matters beyond mathematics
If AI can make discoveries reliably, research teams could pursue questions they currently lack the time or staff to investigate. More promising ideas for medicines and materials could reach experiments and testing.
A system that checks its results and learns from failed attempts could then choose a worthwhile next question and investigate it. Research could continue through many rounds, with each result guiding what to try next.
What the proofs change
ETH concerned puzzles like the dinner above, with many yes-or-no choices and rules that must all hold. Every added choice doubles the possible lists. ETH said even the cleverest method would face some fixed minimum rate of growth in the work required. The new proofs show that this rate can keep falling as puzzles get larger. 5 2
That changes what researchers can rule out. OpenAI says hundreds of papers used ETH to argue that certain tasks could not be solved much faster. A 2026 paper by NUS Computing researchers and colleagues did so for certain geometric problems. Those conclusions have not been shown to be wrong, but ETH can no longer support them. 1 3 4
What to watch next
No practical speed-up has been shown for today's software, and the larger P versus NP question remains open. Both released proofs have passed software checks, while researchers continue to examine their meaning and consequences. 6 9 7 8
The ETH result is a milestone in AI research. The next test is whether AI can make discoveries repeatedly, verify them and use what it learns to choose the next question.
Read the full story to try the dinner puzzle and see what the proofs change.