nPost Blog

The P vs NP problem

See original post at – chris dixon’s blog:

One of the great unsolved questions in computer science is the P vs NP problem. It is one of the seven Millennium Prize Problems – if you solve one of them, you get $1 million and become really famous among mathematicians and computer scientists.

Here’s my non-technical interpretation of the essence of the P vs NP problem:

Can every answer that can be feasibly verified also be feasibly calculated?

What I am calling “feasible” is what computer scientists call algorithms that can run “polynomial” as opposed to “exponential” time.

There are at least four possible outcomes to the attempts to solve this problem: 1) the current situation continues – no proof of anything is found, 2) P=NP is proved true, 3) P=NP is proved false, 4) it is proved that it’s impossible to prove P=NP to be true or false.

If P=NP were proved true, there would be many serious real-world consequences. All known encryption schemes rely on the fact that prime factors of large numbers are something that can be feasibly verified but not calculated. If P=NP, that means there would also be feasible ways to calculate prime factors, and hence decrypt codes without their private keys. So if someone does prove P=NP, he or she should probably inform authorities before publishing the proof and all hell breaks loose (thanks Matt for this observation – you could also imagine a lot of conspiracy theories about what happens to scientists who try to prove P=NP..!)

Most computer scientists seem to suspect P does not equal NP. MIT computer scientist Scott Aaronson gives informal arguments against P=NP in this entertaining blog post, including this philosophical argument:


He follows up with a much longer essay (which I found really interesting but ultimately unconvincing) on the philosophical implications of computational complexity (the field of computer science that studies questions like P vs NP).


About Nathan Kaiser

Speak Your Mind