# P vs NP and Goedel

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

-
What makes you say that? (If that were true, why would people be offering a million dollars to resolve the question?) – Qiaochu Yuan May 4 '11 at 9:26
I don't see the point in cross posting both MO and MSE at the same time, given a few days of wait and nothing would have come up on MO (or vice versa) it would be reasonable to cross post. – Asaf Karagila May 4 '11 at 9:30
Also, being a layman or not you should at least explain why this seems that way to you. – Asaf Karagila May 4 '11 at 9:30
As an interesting aside, Godel wrote a letter to Von Neumann once expressing how, if P=NP, it will be the end of human mathematics, excepting possibly the postulation of axioms. The remark is in this paper (which is well worth a read for most folks here anyway). – EMS Mar 22 '12 at 1:43

## 3 Answers

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.

-

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.

-

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.

-