---
title: 'The one thing holding theoretical CS together just broke... kinda'
source: 'https://youtube.com/watch?v=iw9SZgyahqg'
video_id: 'iw9SZgyahqg'
date: 2026-11-07
duration_sec: 360
channel: 'Fireship'
---

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

> Source: [The one thing holding theoretical CS together just broke... kinda](https://youtube.com/watch?v=iw9SZgyahqg)

## Summary

A recent paper from OpenAI may have disproved the Exponential Time Hypothesis (ETH), a foundational assumption in theoretical computer science. The video explains what ETH is, how a new algorithm broke it, and the implications for hundreds of published papers.

### Key Points

- **The Hypothesis That Holds Theoretical CS Together** [00:01] — The Exponential Time Hypothesis (ETH), proposed in 1999 by Russell Impagliazzo and Mohan Paturi, states that solving 3-SAT requires exponential time. It became a cornerstone assumption for proving lower bounds in hundreds of problems.
- **The Breaking Paper** [00:40] — Dan Roberts, a physicist at OpenAI, published a 67-page paper that included a section disproving ETH. This caused excitement among theorists like Scott Aaronson and Sebastian Bubeck, who called it the biggest surprise in 20 years.
- **Understanding 3-SAT and ETH** [01:09] — 3-SAT is the original NP-complete problem: find a true/false assignment for variables that satisfies all rules (each rule requires at least one of three variables to be true). ETH claims no algorithm can beat brute force (2^N) for 3-SAT.
- **Why ETH Matters** [02:37] — Over 800 papers rely on ETH to prove that certain problems cannot be solved faster. For example, finding a clique of K people or the traveling salesman problem are shown to be hard by reducing them to 3-SAT.
- **The New Algorithm** [03:04] — On October 16, an OpenAI model (the same one that dumped 722 math papers) produced an algorithm solving 3-SAT in roughly 2^(n / sqrt(log n)) time, which is sub-exponential. This disproves ETH.
- **The Novel Technique** [03:29] — Instead of searching, the model counted the total number of solutions, turning the problem into a sum that could be broken into pieces. It then used Hermite interpolation (1800s math) to recover the exact count, faster than any search.
- **Practical Impact (For Now)** [04:07] — The algorithm only beats brute force for N > 10^10,000, so no immediate practical impact. However, Scott Aaronson raised his odds of P=NP from 3% to 5%, and noted that a weaker version of ETH might still hold.
- **Reactions and Caveats** [04:48] — Impagliazzo said the first version of the paper was unreadable and had to be rewritten. OpenAI researchers are not paid and didn't sign anything, suggesting the work was independent.

## Transcript

entire field of theoretical computer science together was a hypothesis that two guys at UC San Diego wrote back in 1999. And last week, it may have just broke. The problem is, I don't think it got the recognition it deserved since it
came right after the entire internet was still hung over from Black October. And right before Anthropic filed to go public, Google announced Gemini 4 carbon. Meta announced it was raising 95 billion to buy more GPUs. Google dropped
12% in a single day. And now all the tech CEOs adding their pronouns back to their bios. But last Monday night, Dan Roberts, a very generically named physicist at OpenAI, published a 67page PDF with a very generically named title.
And buried in that PDF was a section that had Sebastian Bubck, the OpenAI call, calling it the biggest surprise in his 20 years of following computer science. the Scott Aronson, the most famous complexity theorist on the
own grad students frantically running into his office and a random PhD student at UCSD making emergency edits to a thesis he was about to submit. But bound depended on had just stopped existing. In today's video, we'll find
out what the exponential time hypothesis actually means, how a model with no name broke it using a technique no human thought to try, and why 800 published papers now have a problem. It is November 6, 2026, and you're watching
the code report. In order to understand exponential time hypothesis, you'll need to first understand threes, which you may vaguely remember from when you were junior year of college. The idea is that you have a bunch of true false variables
and a list of rules, where each rule says at least one of these three variables has to be true. And your job is to find a setting of variables that satisfies every rule at once. It's the original NP complete problem, which
means if you could solve it fast, you could solve every other NP problem fast. The P would equal NP and you'd become the most hated man in cryptography. The combination, which is 2 to the N of
them. And over the decades, we've got that down to about 1.3 to the N with grew exponentially with the number of variables, no matter what anyone tried. And so in 1999, Russell and Paglazo and Mohan Paturi wrote down the obvious
conclusion and coined the exponential time hypothesis, stating that three satisfiability will always take exponential time and no algorithm will ever fundamentally beat just brute forcing it. Yes, ETH assumes more than P
not equal NP does. But it turned out to be way more useful because if you assume ETH is true, you get a floor on how fast hundreds of other problems can possibly be solved. So that's what everyone did. And as of today, there are more than 800
papers relying on that assumption. For example, there's a well-known proof that finding a group of K people who all follow each other can't be done much group. And the way it works is by showing you that if you could, you could
also solve three satisfiability faster, which ETH says is impossible. Or there's have to find the shortest route that visits every city once. The best known algorithms get exponentially slower with every city you add. And for 27 years,
it couldn't get faster. But then on October 16th, the same internal model that dumped 722 math papers onto GitHub a few weeks earlier, wrote an algorithm that solves threes in roughly 2 to the n
over the square root of log n time, which is still slow, but it's not exponential, which by definition means the exponential time hypothesis is false. And of course, the way the model got there was fairly novel, too. Usually
mathematicians would start flipping switches and checking rules until they either found a setting that worked or ran out of options. But what the model realized was that by counting how many total solutions exist, it could turn the
problem into a giant sum which unlike search could be broken into pieces. But from there, the model tweaked the formula so the rules no longer dependent solutions in each piece separately and then used a piece of 1800's math called
Hermite interpolation to find the exact number of solutions the original untweaked formula had, which turned out to be faster than any search ever written. And that alone was enough to break ETH. Now, before you sell your
Bitcoin, in reality, at least today, this doesn't actually change much, which because the algorithm doesn't beat brute force until N is bigger than 10 to the 10,000. With that said, theoretical computer scientist Scott Aronson bumped
his personal odds of P equals NP from 3% to 5%. And reminded everyone that back in 2016, he wrote a blog post where he gave ETH an 80% chance of being true. His take is now that Impoglazo and Poui were a bit greedy when they wrote down
their hypothesis, and if they had phrased it slightly weaker, it would still be standing today. But if it's any consolation for those two, OpenAI asked They've made it clear that they're not getting paid and they didn't sign
anything, which is also probably why Impliazo said that the first version OpenAI sent over was completely unreadable and they had to rewrite it want to get more out of your coding agents while burning fewer tokens, you
today's video, that they just launched Warp Factories, which helps you build your own software factory in the cloud by giving you flexible infrastructure that's better than whatever factory you asked Opus to vibe coat. Everything gets
configured as code like Terraform but for coding agents. This defines your can talk to, the automations that trigger them, and their cloud sandboxes using any OS. And if you want to cut cost to ape into the anthropic IPO, you
different models and find one that's cheaper and higher quality. Here, I picked out some UI bugs my factory fixed in the past, and Warp replayed all of them against different coding models to find a winner. It's like SWEBench, but
been using this themselves to get their agent cost down from $80 per PR to $20 in just a few weeks. And if you want to do this too, Warp Factories is in early link below. This has been the Code Report. Thanks for watching and I will
Report. Thanks for watching and I will see you in the next one.
