# The one thing holding theoretical CS together just broke... kinda

- Channel: [Fireship](https://www.youtube.com/channel/UCsBjURrPoezykLs9EqgamOA)
- Published: 2026-11-06
- Source video: [Watch on YouTube](https://youtube.com/watch?v=iw9SZgyahqg)
- Read on ReadTube: https://www.read.tube/p/videos/iw9SZgyahqg
- Language: English

## Summary

**AI Algorithm Breaks a Theoretical CS Assumption**

An OpenAI internal model reportedly found a subexponential algorithm for 3-SAT, technically disproving the exponential time hypothesis that has supported lower bounds across theoretical computer science for decades. The approach counts solutions and uses algebraic decomposition and Hermite interpolation rather than searching assignments directly. The result is not practically useful yet, but it could affect more than 800 papers and has modestly increased some researchers’ estimates that P equals NP. The video also promotes Warp Factories, a platform for managing and benchmarking coding agents.

The exponential time hypothesis (ETH) claimed that solving 3-SAT, a foundational NP-complete problem, would always require exponential time. Although ETH is stronger than P ≠ NP, it became especially useful because researchers used it to establish lower bounds for hundreds of other problems, including finding fully connected groups and solving the traveling salesman problem. More than 800 papers reportedly rely on the assumption.

An unnamed internal model at OpenAI produced an algorithm that appears to refute ETH. Instead of searching through variable assignments, the method counts all satisfying assignments, rewrites the resulting sum so its components become independent, and uses Hermite interpolation to recover the exact original count. The resulting runtime is roughly 2^n divided by the square root of log n, which is technically subexponential and therefore contradicts ETH.

The breakthrough has little immediate practical impact because the algorithm would not outperform brute force until the input contained more than 10^10,000 variables. However, it weakens a central theoretical foundation: Scott Aaronson raised his personal estimate that P = NP from 3% to 5%, and suggested that the original ETH may have been stated too strongly. The researchers who introduced ETH were asked to verify the proof, after reportedly finding and rewriting an initially unreadable version.

The video also presents Warp Factories, a sponsored cloud platform for coding-agent workflows. It lets developers configure repositories, secrets, agents, automations, and sandboxes as code, while its benchmarking tools compare models on a developer’s own tasks; Warp says this reduced its agent cost per pull request from $80 to $20.
