6

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$?

Community
  • 1
SpaceTrucker
  • 171
  • 6
  • 2
    This post should be migrated to the (non-research-level) CS stackexchange. – Niel de Beaudrap Oct 18 '12 at 16:09
  • 1
    @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. – Sasho Nikolov Oct 18 '12 at 16:33
  • @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. – Niel de Beaudrap Oct 18 '12 at 16:36
  • A migration would be fine, since I'm merely expecting references to published work. But I also appreciate some interesting thoughts on this topic. – SpaceTrucker Oct 18 '12 at 16:39
  • 1
    actually, SpaceTrucker (space trucker?!) here is the question I recalled seeing http://cstheory.stackexchange.com/questions/10044/implications-of-unprovability-of-p-neq-np. 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. – Sasho Nikolov Oct 18 '12 at 16:41
  • @SashoNikolov SpaceTrucker is fine. I will have a look at the question. – SpaceTrucker Oct 18 '12 at 16:44
  • @SashoNikolov I have flagged my question as a duplicate. – SpaceTrucker Oct 18 '12 at 16:51

1 Answers1

9

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.

Niel de Beaudrap
  • 8,821
  • 31
  • 70
  • The article of Scott Aaronson was, what I was searching for thanks. – SpaceTrucker Oct 18 '12 at 16:49
  • 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). – David Harris Oct 18 '12 at 22:30
  • @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. – Niel de Beaudrap Oct 19 '12 at 18:06