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
6
$\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
    Commented 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
    Commented Apr 8, 2011 at 1:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .