P vs NP and Gödel

Question

I apologize for the, perhaps, silly question. My impression, as a layman, is that Gödel Incompleteness Theorem should rule out the possibility that P=NP. Is that true or there are deeper technical implications?

Answer 1

I'll repeat what I wrote over on MO:

It is true that there is no algorithm to determine whether or not $T$ is proved by PA, and that the proof of this is pretty close to the proof of Godel's theorem. If there were a polynomial $p$ such that every theorem of length $K$ had a proof of length $p(K)$, this would contradict the above fact. (Just trying every proof of length $p(K)$ would be an algorithm.)

It is also true that, if P=NP, there is a polynomial time algorithm such that, if $T$ has a proof of length $N$, then this algorithm finds a proof of length $q(N)$, for some polynomial $q$.

These two facts are not in contradiction, because the first is about proofs of length polynomial in the size of the theorem, and the second is about proofs polynomial in the size of some other proof.

Answer 2

There is no reason to think that the incompleteness theorems have any bearing on the question whether $P=NP$, and no current work has established any relationship between them.

Answer 3

Diagonalization worked well for Gödel's theorem, but the quest to use it to resolve the P versus NP question has been ruled out by the Baker-Gill-Solovay theorem.