Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
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
1  
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
6  
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
1  
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 3

up vote 12 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.