# What is the axiomatic (set theory) context of the P vs NP and NP=EXPTIME conjectures?

When the conjecture $\mathbf{P} = \mathbf{NP}$ or $\mathbf{P} \neq \mathbf{NP}$ is set (e.g. by the Clay Mathematical Institute by S. Cook, see here) what mathematical axiomatic system is assumed?

In order to prove or disprove such statements, you need to assume some axioms. Which ones? Only the Peano (2nd order formal language) arithmetic? The Zermelo–Fraenkel set theory with the axiom of choice? Smaller axiomatic set theories (e.g. Gödel's constructible sets, where the continuum hypothesis holds too, see here)?

Obviously, it should be an axiomatic theory that accepts the countable infinite. But which in particular? Is there any published result that would prove them consistent in a particular axiomatic set theory? (In other words, defining a model in which it is true, but not claiming to be true in all models).

• its generally based on the TM model which has not been shown to have any particular dependence on the choice of set theory axioms... so far!
– vzn
Jul 1, 2014 at 15:23
• You might find this interesting scottaaronson.com/papers/pnp.pdf. Among other very interesting things, the survey talks about why if P vs NP were independent of PA, then we'd almost prove P=NP. For example, independence implies NP is in $\mathsf{DTIME}(n^{\alpha(n)})$ where $\alpha(n)$ is the inverse Ackermann functions. Jul 1, 2014 at 23:27
• see also results in TCS independent of ZFC which indicates roughly "not much so far"...
– vzn
Jul 2, 2014 at 1:44
• @SashoNikolov: if I am not mistaken, what you say is true if independence is proved using currently known general techniques (e.g. forcing, classical realizability, etc.). In fact, the argument you are alluding to rests on the fact that: 1) there are $\Pi^0_1$ sentences implying $P\neq NP$ (such as "$SAT$ does not have quasi-polynomial circuits"); 2) those techniques generate only models satisfying every $\Pi^0_1$ sentence true in the standard model. This shows that current techniques are probably useless for the independence of P vs NP, not that independence is unlikely in general. Jul 2, 2014 at 14:06
• @DamianoMazza Thanks Damiano, you are right, apologies for making an incredibly strong claim. Jul 2, 2014 at 20:16