OpenAI 的无名模型刚刚改变了 P = NP 的几率...

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. 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 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. 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. 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. 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. 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. 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. 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. 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 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. 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. 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 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, 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. 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. 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.