# On the provability of P versus NP

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?

• – Marzio De Biasi Aug 29 '13 at 12:32
• It seems to be me that you have more basic confusion about how can something be true but unprovable. Please check tour and help center for the scope of this site. I think this is more suitable for Computer Science or Mathematics. – Kaveh Aug 29 '13 at 22:48
• this semifamous paper Natural proofs by Razborov/Rudich is applicable to this question – vzn Sep 2 '13 at 15:59
• 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 Sep 4 '13 at 13:31

• 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 Aug 29 '13 at 19:35
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.