An unnamed OpenAI model's subexponential 3-SAT algorithm breaks the 27-year-old exponential time hypothesis — but since the algorithm only beats brute force above n = 10^10,000, practical impact today is nil.
ETH assumes more than P ≠ NP does, but it proved more useful because assuming it gives a floor on how fast hundreds of other problems can be solved.
Source: Russell, Impagliazzo and Paturi, UC San Diego, 1999
Researchers used ETH to prove lower bounds on problems like finding cliques (k people who all follow each other) and the traveling salesman problem.
The result was published in a 67-page PDF by Dan Roberts, a physicist at OpenAI, and was called the biggest surprise in 20 years by OpenAI researcher Sebastian Bubeck.
Source: Dan Roberts, OpenAI, 67-page paper
Solving 3-SAT fast would let you solve every other NP problem fast.
This decades-long pattern is what motivated Impagliazzo and Paturi to write down ETH in 1999.
The paper itself makes clear the practical impact is nil despite the theoretical blow to ETH.
Source: the OpenAI paper
In 2016 he had given ETH an 80% chance of being true; he now says Impagliazzo and Paturi were a bit greedy, and a slightly weaker phrasing of the hypothesis would still be standing.
Source: Scott Aaronson
Impagliazo said the first version OpenAI sent over was completely unreadable and they had to rewrite it before publishing anything.
Source: Impagliazzo and Paturi via OpenAI verification request
The clique lower-bound proof works by showing that a faster clique algorithm would solve 3-SAT faster, which ETH says is impossible.
Searchable transcript of OpenAI’s nameless model just changed the odds of P = NP... — Fireship (06:01). Search for a phrase, then click its timestamp to jump straight to that moment in the video.
Captions sourced from the original video on YouTube, published by Fireship. The video, its captions and all related intellectual property remain the property of their respective owners; AINotes claims no ownership. Provided for research, accessibility and search — see the Transcript Notice and Copyright Policy.
00:00 But for years, the one thing holding the 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.
00:16 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.
00:40 And buried in that PDF was a section that had Sebastian Bubck, the OpenAI researcher from the Navier Stokes phone call, calling it the biggest surprise in his 20 years of following computer science. the Scott Aronson, the most famous complexity theorist on the internet, finding out about it from his 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.
01:02 But because the assumption his entire lower 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.
01:21 In order to understand exponential time hypothesis, you'll need to first understand threes, which you may vaguely remember from when you were high in computer science class in your 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.
01:38 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 obvious approach is to try every combination, which is 2 to the N of them.
01:58 And over the decades, we've got that down to about 1.3 to the N with some clever tricks. But the time always 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.
02:22 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 faster than checking every possible group.
02:46 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 the traveling salesman problem where you 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, nobody worried about it because ETH said it couldn't get faster.
03:06 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.
03:27 Usually when searching for a solution, 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 on each other.
03:50 They counted the 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 the paper itself makes pretty clear because the algorithm doesn't beat brute force until N is bigger than 10 to the 10,000.
04:17 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.
04:40 But if it's any consolation for those two, OpenAI asked them to be the ones to verify the proof. 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 before publishing anything. And if you want to get more out of your coding agents while burning fewer tokens, you need to check out Warp, the sponsor of today's video, that they just launched Warp Factories,
05:04 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 code repos and secrets, the agents you can talk to, the automations that trigger them, and their cloud sandboxes using any OS.
05:23 And if you want to cut cost to ape into the anthropic IPO, you can use factory benchmarks to compare 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 using your own conversations.
05:41 Warp has 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 access for you to get started at the link below. This has been the Code Report. Thanks for watching and I will see you in the next one.