Possible Duplicate:
Implications of unprovability of $P\neq NP$

I shortly came across Gödels incompleteness theorem again and I wondered, since so much time has been spent on trying to answer whether $P = NP$, do we know that such a proof exists? Maybe $P = NP$ is a theorem that can't be answered with the kind of math we are currently working with. Do you know evidence or even a proof that Gödels incompleteness theorem does not apply to whether $P = NP$?

  • 2
    $\begingroup$ This post should be migrated to the (non-research-level) CS stackexchange. $\endgroup$ Commented Oct 18, 2012 at 16:09
  • 1
    $\begingroup$ @NieldeBeaudrap i think there is a research level question in here: is P vs NP provable in ZF/other logical theory. I have a feeling I have seen this question before though. $\endgroup$ Commented Oct 18, 2012 at 16:33
  • $\begingroup$ @SashoNikolov: It is indeed a research question. It's a very good research question. Unfortunately, it is a research question of essentially the same magnitude as P versus NP itself, and our tendancy for such problems which was why I suggested the transfer. My impression is that we prefer here questions which are not only research-caliber, but also with a reasonable probability of being answerable. The reason why I suggested transferring to CS.SE instead is because an easier answer providing just an outline of the idea would be suitable there. But I suppose it can be posted here. $\endgroup$ Commented Oct 18, 2012 at 16:36
  • $\begingroup$ A migration would be fine, since I'm merely expecting references to published work. But I also appreciate some interesting thoughts on this topic. $\endgroup$ Commented Oct 18, 2012 at 16:39
  • 1
    $\begingroup$ actually, SpaceTrucker (space trucker?!) here is the question I recalled seeing cstheory.stackexchange.com/questions/10044/…. Look at the Aaronson survey linked in the question and the wonderful answers by Timothy Chow and Kaveh. I think that should address your question..if it does I'd vote to close as a close duplicate. $\endgroup$ Commented Oct 18, 2012 at 16:41

1 Answer 1


Note that Gödel's Incompleteness Theorems are the following statements:

  1. Any formal system which can be used to express arithmetic is either incomplete (there are statements which are neither provable nor disprovable) or inconsistent.

  2. Any formal system which can be used to prove a statement equivalent to its own consistency, is in fact inconsistent.

But assuming, for instance, that ZF set theory (or an essentially equivalent foundation for mathematical subjects such as computer science) is consistent, we don't need Gödel's Theorems anymore to tell us that there are statements which are neither provable nor disprovable from our foundations: interesting specific examples, such as the Axiom of Choice have already been demonstrated. So even without Gödel's Theorem, it is certainly concievable that a statement such as "P = NP" is indepdendent of set theory.

For this question, Scott Aaronson has written a very accessible article on the subject, which also goes over the basics of formal logic, what it could mean to have a model of set theory which included an axiom which is equivalent to asserting its own inconsistency, and the subject of logical independence results in general.

  • $\begingroup$ The article of Scott Aaronson was, what I was searching for thanks. $\endgroup$ Commented Oct 18, 2012 at 16:49
  • $\begingroup$ The Axiom of Choice is not arithmetical, like P vs NP. I don't think there are any natural arithmetical questions which are known undecidable in ZFC (or any equivalent set theory). $\endgroup$ Commented Oct 18, 2012 at 22:30
  • $\begingroup$ @DavidHarris: I'm curious. What would you say are the properties on an "arithmetical" statement? There certainly is a difference in character between $\mathsf{P} \ne \mathsf{NP}$ and the Axiom of Choice, but "arithmetical" isn't an adjective I would readily apply to either of them. $\endgroup$ Commented Oct 19, 2012 at 18:06

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