It's been a while since I last studied the whole P vs NP thing, but this is much less a big deal that they make it out to be. Not that it's trivial, but I think the article does a good job explaining the problem at the bottom. But in short, here's the deal. If this Babai is correct, then he has proven that it is theoretically possible to design an algorithm to solve for any complex problem in a non-infinite timeframe. That's a big deal in that we didn't know that for sure prior to his proof. But it's not a big deal in that such an algorithm currently doesn't exist (it just theoretically CAN exist... IF Babai's proof is correct) and such an algorithm won't necessarily complete a solution for any given problem before the heat death of the universe (which is a finite time scale, just a very long one). Nor does it even provide for the fact that the hardware required to even compile such an algorithm is completely unknown (and currently unknowable). It could be that the algorithm is of such complexity that we will be completely unable to even guess at the system requirements to run it for centuries or longer, and that's even assuming Moore's Law (processing power doubles every 18 months) holds true. And that's one HELL of a claim for me to make. To understand why that's a hell of a claim, it's important to remember the parable of the vizier who asked to be paid by placing a single grain of rice on the first square on a chessboard and doubling the numbers of grains on each subsequent square (1, then 2, then 4, then 8...). The foolish sultan agreed thinking he'd be giving away a trivial amount of rice, but it bankrupted him. For on the 64th square alone, he'd be required to place over 9 quintillion grains of rice (2^63 = 9,223,372,036,854,775,808). That is the power of simple doubling.
But I can make that claim, because of the fact that this is nothing more than a mathematical proof that such an algorithm could exist. It does not provide what that algorithm is, or what it would possibly take to code that algorithm. So yeah. It's cool. But it's not world changing.
What happened to the science being settled?
ReplyDeleteIt's been a while since I last studied the whole P vs NP thing, but this is much less a big deal that they make it out to be. Not that it's trivial, but I think the article does a good job explaining the problem at the bottom. But in short, here's the deal. If this Babai is correct, then he has proven that it is theoretically possible to design an algorithm to solve for any complex problem in a non-infinite timeframe. That's a big deal in that we didn't know that for sure prior to his proof. But it's not a big deal in that such an algorithm currently doesn't exist (it just theoretically CAN exist... IF Babai's proof is correct) and such an algorithm won't necessarily complete a solution for any given problem before the heat death of the universe (which is a finite time scale, just a very long one). Nor does it even provide for the fact that the hardware required to even compile such an algorithm is completely unknown (and currently unknowable). It could be that the algorithm is of such complexity that we will be completely unable to even guess at the system requirements to run it for centuries or longer, and that's even assuming Moore's Law (processing power doubles every 18 months) holds true. And that's one HELL of a claim for me to make. To understand why that's a hell of a claim, it's important to remember the parable of the vizier who asked to be paid by placing a single grain of rice on the first square on a chessboard and doubling the numbers of grains on each subsequent square (1, then 2, then 4, then 8...). The foolish sultan agreed thinking he'd be giving away a trivial amount of rice, but it bankrupted him. For on the 64th square alone, he'd be required to place over 9 quintillion grains of rice (2^63 = 9,223,372,036,854,775,808). That is the power of simple doubling.
ReplyDeleteBut I can make that claim, because of the fact that this is nothing more than a mathematical proof that such an algorithm could exist. It does not provide what that algorithm is, or what it would possibly take to code that algorithm. So yeah. It's cool. But it's not world changing.