<p>Gödel's incompleteness theorem is really about provability  given a theory with enough expressive power, you'll end up with some statement which can be true in some models, and false in others, hence not provable.
In this case, if P vs NP can't be proved, if you believe that reality is a model of mathematics, P = NP or P $\neq$ NP must still be true in "our world". Hence, as David said, either no polynomial algorithm exists but we won't be able to prove this statement, or a polynomial algorithm does exist but we won't be able to prove that it solves the problem or that it runs in polynomial time.</p>

CC BY-SA 3.0
2013-08-29T22:12:10.683Z
2013-08-31T14:40:07.803Z
2013-08-31T14:40:07.803Z
Tpecatte
<p>If P=NP, there must be polynomial-time algorithms for NP-complete problems.  However, there might not be any algorithm that provably solves an NP-complete problem and provably runs in polynomial time.</p>

CC BY-SA 3.0
2013-08-29T18:25:14.540Z
So, what you are saying, is that the flaw is that there may be an example of a polynomial solution but you may not be able to prove that it is polynomial? Because then it is not considered in the proof by example, so I still don't see the flaw.
Alvaro
CC BY-SA 3.0
2013-08-29T18:50:46.430Z
Suppose that P=NP but this is not provable. This means there is a polynomial time algorithm A for 3-SAT. If you could prove that A was a poly-time algorithm for 3-SAT, that would contradict unprovability of P=NP. Therefore, although it is true that A runs in polynomial time and true that A solves 3-SAT, at least one of these facts cannot be proven.To phrase it in the terms of the question, the fact that a poly-time algorithm for 3-SAT exists does not imply that one "can be found".
David Richerby
CC BY-SA 3.0
2013-08-29T18:55:07.300Z
So, the "But if no example of a polynomial solution for an NP-complete problem can be found, this means that P=NP is false" is wrong, because there can be a solution even though it cannot be found?
Alvaro
CC BY-SA 3.0
2013-08-29T19:19:11.757Z
That's correct.
David Richerby
CC BY-SA 3.0
2013-08-29T19:35:22.007Z
You may want to think about what "can be found" means. while you can enumerate over all turing machines, for each machine $M$ you'd have to show that: there exists an integer $c$ and an integer $N$, such that for all integers $n \geq N$ and all inputs of size $n$, $M$ runs in time at most $n^c$ and decides 3SAT. statements like this are in general not decidable.
Sasho Nikolov
CC BY-SA 3.0
2016-01-09T23:55:29.093Z
If there's a polynomial-time algorithm for 3-SAT, then there's an algorithm that can be proved to solve 3-SAT, but can't be shown to run in polynomial time. Just run the polynomial-time algorithm for 3-SAT in parallel with an exponential-time algorithm that provably solves 3-SAT. Similarly, there's an algorithm that provably runs in polynomial time, but can't be proved to solve 3-SAT. Just stop the algorithm after a polynomial amount of time.
Peter Shor 
CC BY-SA 3.0
2013-08-29T11:34:18.953Z
2013-08-29T11:34:18.953Z
David Richerby
<p>First of all, my understanding on Gödel's incompleteness theorem (and formal logic in general) is very naive, also is my knowledge on theoretical computer science (meaning only one graduate course taken while I'm still an undergraduate), so this question may be very naive.</p>

<p>As far as I could find, the provability of P versus NP is an open problem.</p>

<p>Now:</p>

<ul>
<li>Gödel's first incompleness theorem states that there may be statements that are true but not provable nor disprovable.</li>
<li>If a polynomial solution is found for an NP-complete problem, it proves that P = NP.</li>
</ul>

<p>So, suppose that P=NP is not provable:<br/>
This means that no example of a polynomial solution for an NP-complete problem can be found (otherwise, this would be a proof).<br/>
But if no example of a polynomial solution for an NP-complete problem can be found, this means that P=NP is false (proving it, meaning the statement is provable), which leads to a contradiction, therefore P=NP should be provable.<br/></p>

<p>This sounds like a proof of the provability of P=NP to me, but I think it's extremely likely that it is due to my lack of understanding of the logic topics involved. Could anyone please help me understand what is wrong with this?</p>

CC BY-SA 3.0
2013-08-29T12:32:20.233Z
See [Scott Aaronson's paper "Is P Versus NP Formally Independent?"](http://www.scottaaronson.com/papers/pnp.pdf)
Marzio De Biasi
CC BY-SA 3.0
2013-08-29T22:48:12.653Z
It seems to be me that you have more basic confusion about how can something be true but unprovable. Please check [about] and [help/on-topic] for the scope of this site. I think this is more suitable for [cs.se] or [math.se].
Kaveh
CC BY-SA 3.0
2013-09-02T15:59:04.007Z
this semifamous paper [Natural proofs](http://en.wikipedia.org/wiki/Natural_proof) by Razborov/Rudich is applicable to this question
vzn
CC BY-SA 3.0
2013-09-04T13:31:49.847Z
You may also be interested in Hartmanis' monograph "Feasible Computations and Provable Complexity Properties" which essentially discusses what happens if we only consider problems that are provably in P, provably in NP, etc.
Joshua Grochow
<np-hardness><proofs><p-vs-np>
On the provability of P versus NP
Alvaro
# On the provability of P versus NP

(Asked by: username_0 on 2013-08-29)

First of all, my understanding on Gödel's incompleteness theorem (and formal logic in general) is very naive, also is my knowledge on theoretical computer science (meaning only one graduate course taken while I'm still an undergraduate), so this question may be very naive.

As far as I could find, the provability of P versus NP is an open problem.

Now:

* Gödel's first incompleness theorem states that there may be statements that are true but not provable nor disprovable.
* If a polynomial solution is found for an NP-complete problem, it proves that P = NP.

So, suppose that P=NP is not provable:  
This means that no example of a polynomial solution for an NP-complete problem can be found (otherwise, this would be a proof).  
But if no example of a polynomial solution for an NP-complete problem can be found, this means that P=NP is false (proving it, meaning the statement is provable), which leads to a contradiction, therefore P=NP should be provable.

This sounds like a proof of the provability of P=NP to me, but I think it's extremely likely that it is due to my lack of understanding of the logic topics involved. Could anyone please help me understand what is wrong with this?

**Tags:** np-hardness, proofs, p-vs-np

> **Comments:**
> **username_1**: See [Scott Aaronson's paper "Is P Versus NP Formally Independent?"](http://www.scottaaronson.com/papers/pnp.pdf)  
> **username_2**: It seems to be me that you have more basic confusion about how can something be true but unprovable. Please check [about] and [help/on-topic] for the scope of this site. I think this is more suitable for [cs.se] or [math.se].  
> **username_3**: this semifamous paper [Natural proofs](http://en.wikipedia.org/wiki/Natural_proof) by Razborov/Rudich is applicable to this question  
> **username_4**: You may also be interested in Hartmanis' monograph "Feasible Computations and Provable Complexity Properties" which essentially discusses what happens if we only consider problems that are provably in P, provably in NP, etc.  

---

## 2 answers

### Answer by username_6 on 2013-08-29. Score: 23 | Accepted answer

If P=NP, there must be polynomial-time algorithms for NP-complete problems. However, there might not be any algorithm that provably solves an NP-complete problem and provably runs in polynomial time.

> **Comments:**
> **username_0**: So, what you are saying, is that the flaw is that there may be an example of a polynomial solution but you may not be able to prove that it is polynomial? Because then it is not considered in the proof by example, so I still don't see the flaw.  
> **username_6**: Suppose that P=NP but this is not provable. This means there is a polynomial time algorithm A for 3-SAT. If you could prove that A was a poly-time algorithm for 3-SAT, that would contradict unprovability of P=NP. Therefore, although it is true that A runs in polynomial time and true that A solves 3-SAT, at least one of these facts cannot be proven.To phrase it in the terms of the question, the fact that a poly-time algorithm for 3-SAT exists does not imply that one "can be found".  
> **username_0**: So, the "But if no example of a polynomial solution for an NP-complete problem can be found, this means that P=NP is false" is wrong, because there can be a solution even though it cannot be found?  
> **username_6**: That's correct.  
> **username_7**: You may want to think about what "can be found" means. while you can enumerate over all turing machines, for each machine $M$ you'd have to show that: there exists an integer $c$ and an integer $N$, such that for all integers $n \geq N$ and all inputs of size $n$, $M$ runs in time at most $n^c$ and decides 3SAT. statements like this are in general not decidable.  
> **username_8**: If there's a polynomial-time algorithm for 3-SAT, then there's an algorithm that can be proved to solve 3-SAT, but can't be shown to run in polynomial time. Just run the polynomial-time algorithm for 3-SAT in parallel with an exponential-time algorithm that provably solves 3-SAT. Similarly, there's an algorithm that provably runs in polynomial time, but can't be proved to solve 3-SAT. Just stop the algorithm after a polynomial amount of time.  

---

### Answer by username_5 on 2013-08-29. Score: 6

Gödel's incompleteness theorem is really about provability given a theory with enough expressive power, you'll end up with some statement which can be true in some models, and false in others, hence not provable.
In this case, if P vs NP can't be proved, if you believe that reality is a model of mathematics, P = NP or P $\neq$ NP must still be true in "our world". Hence, as David said, either no polynomial algorithm exists but we won't be able to prove this statement, or a polynomial algorithm does exist but we won't be able to prove that it solves the problem or that it runs in polynomial time.


---

