cdixon blog

The P vs NP problem

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:

If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it?

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).