Why is $\mathsf{P}$ vs. $\mathsf{NP}$ problem considered so important?

Is $\mathsf{P}$ vs. $\mathsf{NP}$ the hardest mathematical problem?

Why is it so hard?

All I'm looking for is the hindrances to solving $\mathsf{P}$ vs. $\mathsf{NP}$. Are there any theorems that help explain why $\mathsf{P}$ vs. $\mathsf{NP}$ is so hard?

  • 9
    $\begingroup$ Am voting to close: too open ended and will lead to discussion rather than any kind of answer. $\endgroup$ – Suresh Venkat Aug 23 '10 at 20:26
  • $\begingroup$ I believe that now only users with rep over 500 can close a question (only five users). I suggest using this question to get the attention of the top users to closing questions: meta.cstheory.stackexchange.com/questions/76/… $\endgroup$ – Shane Aug 23 '10 at 20:42
  • $\begingroup$ Hi guys, I am going to up-vote the question. Basically, although the phrasing is a little broad, I see this as a question about barriers, and while it so happens the wikipedia page covers them main ones, the only way to know that they are fully covered is to ask. Perhaps someone more familiar with the material than me could offer a fuller description of these? $\endgroup$ – Joe Fitzsimons Aug 23 '10 at 22:04
  • 5
    $\begingroup$ Perhaps the question should be reworded along the lines of "Are there any theorems or examples that help explain why P vs NP is so hard?" $\endgroup$ – Joshua Grochow Aug 23 '10 at 22:36
  • 2
    $\begingroup$ @teknikqa: When I said "reworded" I meant to suggest that the original text of the question be erased. I agree with the others that the original way it was phrased ("Is it [the hardest problem to solve]? Why is it so hard") is indeed too open-ended. $\endgroup$ – Joshua Grochow Aug 24 '10 at 6:19

I guess the best answer to your question is to point out that there have been several "barriers" to proving the P vs NP problem which have been identified and which rule out a number of approaches to a proof.

The three main barriers identified are relativization, natural proofs and algebrization. All of these are described on the P vs NP Wikipedia page under the heading "Results about the difficulty of proof", here.

A more detailed explanation can be found in the papers outlining these barriers referenced on the same Wikipedia page.


Here is a thorny difficulty that nullifies many naive attempts at proofs of lower bounds. It's not a theorem per se, but it's a salient example. Many attempts at lower bounds try to define some sort of "complexity function." These complexity functions often have the property that if a circuit C is composed of two circuits F and G and one additional gate, then the complexity of C is at least the complexity of F and G. But this phenomenon is strongly violated by our usual notion of complexity, as the following argument (which I think is due to Razborov) shows.

By a counting argument (originally due to Shannon, I believe) almost all functions require circuits of size $\Omega(2^{n}/n)$ to compute. Let R be a random function, which is therefore highly likely to be hard to compute. Let S=1-R. S is necessarily as hard as R to compute. But S+R=1, a constant function, which is as trivial to compute as possible.

  • $\begingroup$ Nice observation. Are you hinting at the redundancy of NP-complete sets? $\endgroup$ – Mohammad Al-Turkistany Feb 8 '13 at 13:12
  • $\begingroup$ @MohammadAl-Turkistany: I don't see what this has to do with redundancy - can you expand your thought a little? I also don't see what it has to do with NP-complete sets per se - note that I didn't actually say anything about NP in particular, but just about circuits in general. $\endgroup$ – Joshua Grochow Feb 8 '13 at 15:46
  • $\begingroup$ I guess redundancy plays major role in the complexity of problems. According to this paper, Every NP-complete set A splits into two NP-complete sets A1 and A2. blue.utb.edu/lzhang/gpsz06-mitosis.pdf $\endgroup$ – Mohammad Al-Turkistany Feb 8 '13 at 15:54
  • $\begingroup$ I agree redundancy plays an important role, I just don't see how that's related to my answer. $\endgroup$ – Joshua Grochow Feb 8 '13 at 16:22
  • $\begingroup$ Circuits $F$ and $G$ could be identical, nevertheless they can be combined in many ways to produce new circuit $C$. $\endgroup$ – Mohammad Al-Turkistany Feb 8 '13 at 16:27

The patronizing answer is that it amounts to a non-existence proof.

If P != NP (as is commonly considered to be very likely), then proving it amounts to proving that something doesn't exist. Proofs of that type tend to be fairly simple (Comparison sort can't be faster than O(n log n) because it take that many comparisons/bits to be able to enumerate all reordering. A solution to the halting problem directly leads to a contradiction.) or darn near impossible (Fermat's Last Theorem, the four color map problem)

  • 3
    $\begingroup$ Lower bound proofs actually usually tend to be quite hard. I'm not sure the decision tree lower bound for sorting indicates in any way the complexity of P vs. NP. $\endgroup$ – arnab Aug 24 '10 at 3:08
  • $\begingroup$ @arnab: My point exactly. And I wasn't connecting sorting to P vs. NP $\endgroup$ – BCS Aug 24 '10 at 3:23

P vs NP is hard because P != NP.

Please, read this excellent post by Scott Aaronson: http://scottaaronson.com/blog/?p=459 (It may be too big to fit as answer here)


Not the answer you're looking for? Browse other questions tagged or ask your own question.