The P vs NP problem











18 thoughts on “The P vs NP problem

  1. nateberkopec says:

    I liked Notch’s quantum-suicide-computer solution:

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

  4. 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.”

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

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

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

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

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

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

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

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

  13. Pingback: Trackback

Leave a Reply


You are commenting using your account. Log Out / Change )

Twitter picture


Facebook photo


Google+ photo


Connecting to %s