13:52
I did not think this would happen in my lifetime. Let me try to explain. For many decades now, computer scientists have been thinking up devilishly difficult problems and found that trying to solve some of them takes incredibly long. Some of them would take a quadrillion years to solve by brute force. But we humans have invented so many amazing algorithms. We can write programs that simulate light rays to imagine never before seen scenes. I love this so much. And we can write physics simulations to create really lifelike or imaginary worlds. Absolutely ingenious human developed techniques. And you are saying that some problems just cannot be solved efficiently. Well, that is exactly what the exponential time
hypothesis says. It says that some problems are cursed and might always remain so. Here is a cursed problem. The cat is sleeping or the dog is barking or the robot is dancing. When is this true? Well, just make the cat sleep. Problem solved. Easy peasy. What is Carlo even talking about? Get out of here. No, no, no, no. Wait. Let's add another line. The cat is awake or the dog is silent or the robot is dancing. Now, the first one wants the cat to sleep.
The second one wants the cat to be awake. So we have to look for help with a different variable. Let's look at the dog. Oh my, same problem. The dog is barking in the first, silent in the second. But wait, the robot is luckily dancing on both. So that can satisfy both lines. Hooray! But the point here is that one line was very simple, but two lines needed a bit of computation. Still simple, of course. And now you will see the crazy part. We call this the three satisfiability problem, and if you increase the problem size with more animals and lines, what happens? Well, just get a processor that goes through a billion combinations per second, and you are done instantly, right? Not quite. This computer program
would take so long, it might never finish. Well, it could take 1 quadrillion years to finish if we check every combination. Well, then. This is so many combinations, so better write an algorithm that does it a smarter way and do it a lot quicker. And here comes the crazier part. We couldn't. Nobody had ever been able to do that in the general case. Yes, we can be quicker than just trying all the combinations. We have smart algorithms, but none of them could defeat the exponential barrier. This is called the exponential time hypothesis. So, it's over, right? Do we have no hope left to solve this?
Dear fellow scholars, this is Two-Minute Papers with Dr. Károly Zsolnai-Fehér. Well, all this drivel means that this problem is cursed. Cursed how? Well, cursed in a sense that as the problem size grows even just a tiny bit, it gets much harder. In the worst case, exponentially harder. Ew. Now, we can't prove it, but so many people believe it to be true that many papers have been written assuming that this is true and building on that. And then, something insane just happened. Hold on to your papers, fellow scholars, because the age of AI has led us into a breakthrough. OpenAI published a research paper where they say they proved that this hypothesis is not true.
They say that it is possible to defeat the exponential barrier. I'm going to be honest, I did not think this would happen within my lifetime, and it just did. If the proof gets properly verified, it looks increasingly convincing, but the expert review is not 100% done yet. But, if it holds up, then one of the most important assumptions of theoretical computer science has just fallen. That is insanity. Now, I will note that this is not to be confused by the P \{question mark\} = NP problem. That has not been solved. Now, you could say, "Okay, Karoly, but who cares about this silly satisfiability problem? Just bring your dogs and cats elsewhere." Well, I say you have to consider Karp reductions. Before you ask, no, this
does not mean shrinking a fish. It means something completely different. Imagine you have to deliver life-saving medicine to hundreds of hospitals, and you're a bit low on gas. You need the most efficient route. Or, imagine you have to assign radio frequencies to thousands of transmitters, so they can talk without too much interference. Or, place the fewest number of sensors needed to monitor an entire system. Or, select the most valuable scientific equipment to load it onto a small spacecraft. All of these are very different problems, except that they are not. All of these problems can be molded to look like our three satisfiability problem with the cats and dogs. You take your roads and
transform them into a dog and cat question. That is Karp reduction. Wait, and does that mean that Oh, yes. Yes, it does. If you can write an algorithm that can do that one problem faster, it could work for all of these problems, and then even more. Not always, but it's often the case. And that is why this work is so incredibly surprising and valuable. Plus, it gets better. The paper reveals not just the proof that such an algorithm exists. The paper actually gives us the algorithm. And it gets even better. It not only finds the solution, but also tells us exactly how many solutions are there. This is a historic moment in our lives.
What a time to be alive. And just to demonstrate how incredibly efficiently scientists can communicate with each other. All of this summed up in short, "A sub-exponential bound has been claimed for 3-SAT, refuting the exponential time hypothesis." Very concise and super awesome. If you enjoyed this, consider subscribing and hitting the bell. We have a lot more papers coming, and if everything goes well, an interview with Spencer Huang as well. Very fun. I use Lambda to reproduce AI research papers often in minutes. It's also great to train your own models or fine-tune an existing one. Run inference or text-to-image or video, easy peasy. Running a deep seek chatbot or agent, super fast, super reliable.
Lambda gives you powerful NVIDIA GPUs to run your own experiments. I test ideas from the papers I cover, and moments later, results. Love it. Seriously, try it out now at lambda.ai/papers.
