Summary
For 27 years, the Exponential Time Hypothesis (ETH) has underpinned a huge body of theoretical computer science. Fireship’s Code Report looks at how an unnamed internal OpenAI model may have just broken it, following a 67-page PDF from OpenAI physicist Dan Roberts.
The video explains the background: 3-SAT, the classic NP-complete problem, and why Russell Impagliazzo and Ramamohan Paturi’s 1999 hypothesis became a foundation for hundreds of other results, including lower bounds on clique-finding and the traveling salesman problem. More than 800 published papers rely on the assumption. According to the video, on October 16th the model produced an algorithm solving 3-SAT in roughly 2^(n/√log n) time, which is not exponential.
The technique is the interesting part. Instead of searching for a satisfying assignment, the model counted total solutions, turned the problem into a sum that could be split into independent pieces, and used Hermite interpolation, a 19th-century method, to recover the exact count for the original formula.
The video also adds important caveats: the algorithm doesn’t beat brute force until n exceeds 10^10,000, so practical impact is nil for now. It covers reactions from Scott Aaronson, who nudged his odds of P=NP from 3% to 5%, and Sébastien Bubeck, and notes that Impagliazzo and Paturi were asked to verify the proof.
📺 Source: Fireship · Published November 06, 2026
🏷️ Format: News Analysis
