P = NP problem solved?
Pretty big news breaking today about a possible breakthrough on the P vs NP problem, probably the most important unsolved problem in computer science today. Everyone suspects, to a degree bordering on knowledge, that P != NP, but no one has been able to prove that it is the case. Falsifying this belief (that is to say, proving that P = NP) would be rather catastrophic for cryptography and very shocking to everyone in computer science, although perhaps it would also unlock amazing new possibilities in computer algorithms. According to a recently distributed (leaked?) paper, cryptographers can remain calm since P != NP. Even though this is what people believe, its proof would be a significant milestone for computer science.
I promptly downloaded the paper, and as I suspected it was way out of my ability to comprehend without looking things up every few seconds at least, so if I really want to dive into the proof, I’d have to devote a lot more time to it, and if I really want to understand it I will have to devote years of study to complexity theory — assuming I’m smart enough to even get there. Nevertheless, if you want to take a look at the paper, but don’t want to download it from the login-required Scribd link that everyone seems to be sharing, you can grab it here.
August 9th, 2010 at 09:07:05 am
Is the headline a joke, or a typo? :-)
Maybe we should organize a readthrough or discussion or presentation here—someone at FB has to have the chops to understand the paper.
August 9th, 2010 at 11:48:41 am
Ah, the joys of writing blog posts at 2 am.
August 9th, 2010 at 12:13:22 pm
I’ll listen to anybody that has the ability to explain this.
August 10th, 2010 at 01:23:15 am
a;though :)
August 10th, 2010 at 06:28:56 am
Fixed. Thanks!
August 10th, 2010 at 01:19:55 pm
Although there have been many claimed proofs of P != NP, this is one of the few to have much credibility, hence the excitement. But it will take months or years to verify and to repair all of the flaws that are almost certainly in there.
Also, I’m not sure that finding P = NP would necessarily shatter the field of cryptography. These deep theoretical results usually take a while to have much (if any) practical relevance. For example, although we have a proof that PRIMES is in P, the actual primality test that results from the proof is much slower than the previously existing methods.
Say someone showed that there exists an O(n^20) solution to k-SAT. It would make waves, but I don’t think anyone would worry very much about security.