8
$\begingroup$

I was pondering the fact that maybe the classical hard complexity-theoretic questions are undecidable, not because they are so themselves, but because some set-theoretic foundations makes the complexity-theoretic foundations shaky.

My thoughts was that perhaps something like the Continuum hypothesis makes P vs NP undecidable. So my question is, is there a "finitary" or otherwise obviously sane environment for complexity theory that would discount this theory immediately? I'm aware of simpler structures where P vs NP has been decided, but I don't know how that would fit in.

I apologize in advance if this doesn't make sense.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
7
$\begingroup$

The statement that P=NP can be expressed in first-order arithmetic, and that part of mathematics is unaffected by the known methods of proving set-theoretic independence results (forcing, inner models).

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Andreas: Though it is true that something like CH bears no effect on these problems, there are also techniques for producing non-standard models, such as the methods developed by Harvey Friedman. They were devised so we can obtain, for example, independence of certain arithmetic statements from ZFC. $\endgroup$
    – Andrés E. Caicedo
    Apr 7, 2011 at 19:04
  • $\begingroup$ I think it is possible than P=NP is independent of ZFC. There are no obvious obstructions to this statement. $\endgroup$
    – user6976
    Apr 8, 2011 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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