MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
A related question that have led to many answers is – Gil Kalai Apr 7 '11 at 18:46
Nice catch, also the paper linked to there, seems very useful. – kastberg Apr 7 '11 at 19:31
up vote 6 down vote accepted

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).

share|cite|improve this answer
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. – Andrés E. Caicedo Apr 7 '11 at 19:04
I think it is possible than P=NP is independent of ZFC. There are no obvious obstructions to this statement. – Mark Sapir Apr 8 '11 at 1:42

Your Answer


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.