Last summer, Vinay Deolalikar claimed to have proved that P!=NP. This kicked up some terrific math and computer science dust, and a lot of people got excited, myself included. But this wasn't exactly a surprising result...most people suspect that P != NP after all, but a proof has been elusive.
Well, evening out the playing field, Vladimir Romanov claims to have come up with a polynomial time algorithm for 3-SAT -- one of the foundational NP-hard problems. Here's the paper describing the work. But what's more...there's source code for it. If he's right, then P==NP.
I fully expect that people will be picking this work apart pretty rigorously over the next few weeks, months and years. But if it holds up, it's a really big deal. Much bigger than P!=NP, most specifically because it implies that large factorization can be solved in polynomial time, which means all of our encryption is broken.
No comments:
Post a Comment