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

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

CC BY-SA 3.0
2013-02-08T13:12:21.540Z
Nice observation. Are you hinting at the redundancy of NP-complete sets?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-02-08T15:46:51.253Z
@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.
Joshua Grochow
CC BY-SA 3.0
2013-02-08T15:54:48.623Z
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. http://blue.utb.edu/lzhang/gpsz06-mitosis.pdf
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-02-08T16:22:19.363Z
I agree redundancy plays an important role, I just don't see how that's related to my answer.
Joshua Grochow
CC BY-SA 3.0
2013-02-08T16:27:05.820Z
Circuits $F$ and $G$ could be identical, nevertheless they can be combined in many ways to produce new circuit $C$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2010-08-24T06:25:20.697Z
2013-02-08T15:42:52.317Z
2013-02-08T15:42:52.317Z
Joshua Grochow
<p>P vs NP is hard because P != NP.</p>

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

CC BY-SA 2.5
2010-08-24T17:11:34.997Z
2010-08-24T17:11:34.997Z
Vag
<p>The patronizing answer is that it amounts to a non-existence proof.</p>

<p>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 <code>O(n log n)</code> 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 (<a href="http://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem" rel="nofollow">Fermat's Last Theorem</a>, the <a href="http://en.wikipedia.org/wiki/Four_color_theorem" rel="nofollow">four color map problem</a>)</p>

CC BY-SA 2.5
2010-08-24T03:08:49.903Z
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.
arnab
CC BY-SA 2.5
2010-08-24T03:23:03.823Z
@arnab: My point exactly. And I wasn't connecting sorting to P vs. NP
BCS
CC BY-SA 2.5
2010-08-24T01:19:44.880Z
2010-08-24T01:19:44.880Z
BCS
<p>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.</p>

<p>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", <a href="http://en.wikipedia.org/wiki/P_versus_NP_problem#Results_about_difficulty_of_proof">here</a>.</p>

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

CC BY-SA 2.5
2010-08-23T21:56:36.100Z
2010-08-23T21:56:36.100Z
Joe Fitzsimons
<p>Why is $\mathsf{P}$ vs. $\mathsf{NP}$ problem considered so important?</p>

<p>Is $\mathsf{P}$ vs. $\mathsf{NP}$ the hardest mathematical problem? </p>

<p>Why is it so hard?</p>

<p>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?</p>

CC BY-SA 2.5
2010-08-23T20:26:26.670Z
Am voting to close: too open ended and will lead to discussion rather than any kind of answer.
Suresh Venkat
CC BY-SA 2.5
2010-08-23T20:42:20.443Z
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: http://meta.cstheory.stackexchange.com/questions/76/close-these-questions
Shane
CC BY-SA 2.5
2010-08-23T22:04:40.553Z
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?
Joe Fitzsimons
CC BY-SA 2.5
2010-08-23T22:36:36.600Z
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?"
Joshua Grochow
CC BY-SA 2.5
2010-08-24T02:00:02.600Z
@Joshua That is exactly what I wanted to know. Thanks.
teknikqa
CC BY-SA 2.5
2010-08-24T06:19:33.703Z
@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.
Joshua Grochow
<cc.complexity-theory><ds.algorithms><np-hardness>
Why is P vs. NP so hard?
teknikqa
# Why is P vs. NP so hard?

(Asked by: username_0 on 2010-08-23)

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?

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness
> **Comments:**
> **username_1**: Am voting to close: too open ended and will lead to discussion rather than any kind of answer.  
> **username_2**: 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: http://meta.cstheory.stackexchange.com/questions/76/close-these-questions  
> **username_3**: 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?  
> **username_4**: 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?"  
> **username_0**: @Joshua That is exactly what I wanted to know. Thanks.  
> **username_4**: @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.  

---

## 4 answers

### Answer by username_3 on 2010-08-23. Score: 12 | Accepted answer

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](http://en.wikipedia.org/wiki/P_versus_NP_problem#Results_about_difficulty_of_proof).

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


---

### Answer by username_4 on 2010-08-24. Score: 9

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.

> **Comments:**
> **username_5**: Nice observation. Are you hinting at the redundancy of NP-complete sets?  
> **username_4**: @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.  
> **username_5**: 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. http://blue.utb.edu/lzhang/gpsz06-mitosis.pdf  
> **username_4**: I agree redundancy plays an important role, I just don't see how that's related to my answer.  
> **username_5**: Circuits $F$ and $G$ could be identical, nevertheless they can be combined in many ways to produce new circuit $C$.  

---

### Answer by username_6 on 2010-08-24. Score: -2

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)


---

### Answer by username_7 on 2010-08-24. Score: -2

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](http://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem), the [four color map problem](http://en.wikipedia.org/wiki/Four_color_theorem))

> **Comments:**
> **username_8**: 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.  
> **username_7**: @arnab: My point exactly. And I wasn't connecting sorting to P vs. NP  

---

