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 Caro 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'll 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 one 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. Koa Eher. Well, all this dril 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 equals NP problem. That has not been solved. Now, you could say, "Okay, Caro, but who cares about this silly satisfiability problem? Just bring your dogs and cats elsewhere." Well, I say you have to consider carp 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 are 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 carp reduction. Wait, and does that mean that? Oh yes. [laughter] 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 subexponential bound has been claimed for three set refuting the exponential time hypothesis. Very concise and super awesome. If you enjoy 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. Ei peepers.
Generated algorithmically for Search Engine
Indexing.