# Are problems in complexity theory dependent on set theory?

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.

-
A related question that have led to many answers is mathoverflow.net/questions/50023/independence-of-p-np – Gil Kalai Apr 7 '11 at 18:46
Nice catch, also the paper linked to there, scottaaronson.com/papers/pnp.pdf seems very useful. – kastberg Apr 7 '11 at 19:31