Thursday, January 20, 2011

P == NP. The battle rages on.

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: