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

19 thoughts on “The P vs NP problem”

1. nateberkopec says:

I liked Notch’s quantum-suicide-computer solution: http://notch.tumblr.com/post/10526684412/o-1-np-solving-using-the-mqsc

EDIT: In addition, to give people some context, NP problems can be seemingly commonplace. The “travelling salesman” problem of calculating the shortest route between many points is one, and has many practical applications in logistics.

It turns out humans may even be better at solving NP than computers. When presented with “travelling salesman” problems, most human test subjects can draw a better solution, faster, than most computer algorithms.

2. Moses Nakamura says:

@nateberkopec:disqus be careful not to confuse solving NP-complete problems with executing a “good enough” heuristic solution.

3. I’m curious about your thoughts on the philosophical implications?  What did you find unconvincing for instance?

4. 1. I think it’s a leap to assume
Creating : verifying factoring primes :: creating : verifying beautifulness of Mozart’s music.
2. In the longer essay, I found many of the arguments unconvincing. E.g He tried to reconcile Searle’s “Chinese Room” experiment by saying it is infeasible. Even if infeasible, the very idea that a lookup process could outwardly perfectly simulate a true thinking process should make us question whether simply appearing to think == actually thinking.

5. Yeah that bugs me too.   Sure it’s much sexier to talk about appreciating a symphony versus composing one, but this leads to lots of badly written popular science articles.  There’s a whole world of detail wrapped up in the words “feasible,” “verified” and “computed.”

6. I wish I could understand what you are talking about.  It sounds fascinating.

7. hm. I was trying to take technical concepts (which I only partially understand) and make them understandable to non-technical people. If I didn’t do that, then this post failed.

8. Fascinating, but I didn’t get the relationship with startups.

9. ha, no relationship with startups. this is just my personal blog. i thought about writing CS stufff elsewhere but then thought it was a better to just write what i’m interested in here.

10. thepriceofriceinchina says:

Um. P=NP.  I proved it exactly 3 years ago.  I just lost the napkin.

11. dkural says:

Note that proving it true or false has nothing to do with which world we inhabit in.   The continuum hypothesis, for example, is completely independent from the rest of Set Theory. One can do mathematics with our without it.   Which one corresponds to our “universe”?

Establishing (4) in your post  could come in the form of proving that P=NP is independent of ZFC  (i.e. Set Theory + Continuum Hypothesis).   Then we’d still have to figure which universe we live in.

Perhaps the most accessible example of this sort of thing is Euclid’s 5th Postulate, also known as the parallel postulate.   People tried for two thousand years to prove this from the other postulates,  but failed to do so.

Turns out it is “independent” from the other axioms — it is impossible to prove or disprove it…   but we still had to figure out what the geometry of our universe looks like!  Although the 5th postulate is mathematically independent from the rest,   for some given geometries it is either true or false.

It turns out that the most natural formulation of the geometry of space time, according to Einstein’s special relativity theory is not in Euclidean space, but Minkowski Space.

12. I wish more startup bloggers would go “off topic” like this! Startups are about solving real world problems. Doing that well means thinking about interesting things outside of startup-land.

13. Yeah, and just because an algorithm exists doesn’t mean evolution has programmed it into human brains.  It’s pretty obvious in fact that human brains can’t solve NP problems feasibly.

14. In particular, from an AI perspective, it seems fairly clear that the difficulty of doing things like producing symphonies has relatively little to do with NP-hard problems. SAT-solving is NP-hard and yet computers are very good at doing it, much better than humans are. Why are computers not good at composing symphonies, not even really beginner-level good? NP-completeness can’t explain why symphonies are harder than SAT; difficulty of formalization I think is closer to the mark.

Aaronson’s post spurred me to write some more in that vein a few months ago.

15. ZekeV says:

I think I read somewhere that public key encryption is not really NP-hard. So the advent of quantum computing could possibly render public keys useless for encrypting communications without necessarily proving P=NP.

16. tedstockwell says:

Search and data crunching problems can easily be in NP in the general case, but with narrower special cases that fall into P.

Either the problem is constrained to avoid NP, or simply that algorithms may be possible that produce pretty good solutions for real-world data, even if they are not optimal for the general case.

There are plenty of opportunities for startups finding better ways to extract value from ever larger data sets.

On the other hand, if your startup falls on the wrong side of the P/NP boundary, you might craft a beautiful prototype that cannot be scaled.