<p>It's not specified. When there is a serious enough candidate paper purporting to resolve P ≟ NP, a Special Advisory Committee will be formed to decide whether (and to whom) to award the prize. I presume that the Special Advisory Committee will decide whether your system of axioms is acceptable. If you assume Z-F with choice, I guarantee you they will take it. If you assume P ≠ NP as an axiom, I guarantee you they won't.</p>

CC BY-SA 3.0
2014-07-01T13:55:07.867Z
It would be quite interesting/bizarre if choice is required for the proof (i.e. ZFC works, ZF doesn't).
usul
CC BY-SA 3.0
2014-07-01T15:14:57.997Z
I thank the people for their answers so far. It makes sense that it is not specified and it is variable which axiomatic (set theory)  system is assumed. It seems to me that  in a quite restrictive axiomatic set theory (or restrictive model of axiomatic set theory) it is more probable that one can prove that NP=EXPTIME and in a more pluralistic (axiomatic system or model of set theory) more probable that NP is not EXPTIME (finer grades of complexity differences).
Constantine Kyritsis
CC BY-SA 3.0
2014-07-01T15:15:32.563Z
And even it might happen that one can come with a proof, that inside Peano Arithmetic (with sets definable from logical formulas only without axioms of set theory) the famous conjectures are independent and not provable (Unless there is already a result about these conjectures inside Peano Arithmetic or a simpler impossibility argument which I do not know).
Constantine Kyritsis
CC BY-SA 3.0
2014-07-01T15:47:27.537Z
And I even dare to say that inside Zermelo-Frankel set theory with axiom of choice , it may be that P=NP or NP=EXPTIME are non-provable and independent. There is an analogy. Polynomial time complexity corresponds to countable infinite N0 and exponential time complexity corresponds to the cardinality of the Power set of the naturals 2^N0. For decades researchers were wondering if there is any other cardinality between them. Goedel (1940) and Cohen (1963) finally proved that both are independent axioms. There is a similar well known proof that corresponds naturalsto ordinals ( Goodstein Theorem)
Constantine Kyritsis
CC BY-SA 3.0
2014-07-01T15:50:03.203Z
Unfortunately if ones proves the independence of P vs NP conjecture   it seems that he will not be awarded by the Clay mathematical institute 1m , which seems to me unfair
Constantine Kyritsis
CC BY-SA 3.0
2014-07-01T16:01:18.670Z
@drKCostas: I think that depends on the decision of the Board of Directors of the CMI and any Special Advisory Committee they convene in that case.
Peter Shor 
CC BY-SA 3.0
2014-07-01T19:01:20.503Z
I think you can safely assume that if you prove (for example) that it's independent of ZFC then they'd pay out, on the same basis that Hilbert's 10th problem is considered solved. In practice the proof of independence might come in two legs (you prove P=NP is consistent and then I prove P!=NP is consistent) and then they have to make a call. Or you might prove that it's independent of Peano but not know whether AC resolves it, then Peter proves AC implies P=NP. Again you're at their mercy but don't worry, do that and the CS community will find you a job!
Steve Jessop
CC BY-SA 3.0
2014-07-02T18:53:05.197Z
Well said! I admit, I had forwarded a week ago to Stephen Cook, and the president of the Clay mathematical institute, an email that was suggesting to modify the awarded  conjecture, from 2 cases P=NP, P!=NP to 3 cases, the third being that someone proved that both P=NP, P!=NP are independent in ZFC. To be more precise, I was suggesting to Scott Aaronson to requested this modification, as he was the author of the paper here http://www.scottaaronson.com/papers/pnp.pdf
Constantine Kyritsis
CC BY-SA 3.0
2014-07-03T19:43:10.607Z
No one seriously thinks that P != NP is independent of ZFC. We don't know of any non-contrived mathematical statements that are independent of ZFC (other than the obvious Godelian ones). This outcome just isn't going to happen.
David Harris
CC BY-SA 3.0
2014-07-06T08:09:44.850Z
@David Harris I think I just mentioned above, the continuum hypothesis which is a natural statement in ZFC, which has been proved independent. Even in Peano arithmetic, there is a natural statement (Goodstein theorem in ZFC see http://en.wikipedia.org/wiki/Goodstein's_theorem) which is independent in Peano.
Constantine Kyritsis
CC BY-SA 3.0
2014-07-10T08:41:11.973Z
@usul: It's not just bizarre, it is in fact impossible. ZFC is conservative over ZF for arithmetical statements.
Emil Jeřábek
CC BY-SA 3.0
2014-07-01T13:30:46.870Z
2014-07-01T13:30:46.870Z
Peter Shor 
<p>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 <a href="http://www.claymath.org/sites/default/files/pvsnp.pdf">here</a>) what mathematical axiomatic system is assumed?</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory">Zermelo–Fraenkel set theory</a> with the axiom of choice? Smaller axiomatic set theories (e.g. Gödel's constructible sets, where the continuum hypothesis holds too, see <a href="http://mathpost.asu.edu/~sjgm/issues/2005_spring/SJGM_rogers.pdf">here</a>)?</p>

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

CC BY-SA 3.0
2014-07-01T14:19:55.397Z
It is, for any problem in NP, possible to construct a solver S for the problem, such that P=NP implies that S is polynomial.  This makes it unlikely that P=NP is unprovable.
Taemyr
CC BY-SA 3.0
2014-07-01T15:23:01.753Z
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
CC BY-SA 3.0
2014-07-01T23:27:10.383Z
You might find this interesting http://www.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.
Sasho Nikolov
CC BY-SA 3.0
2014-07-02T01:44:23.173Z
see also [results in TCS independent of ZFC](http://cstheory.stackexchange.com/questions/5934/results-in-theoretical-cs-independent-of-zfc) which indicates roughly "not much so far"...
vzn
CC BY-SA 3.0
2014-07-02T14:06:19.623Z
@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_.
Damiano Mazza
CC BY-SA 3.0
2014-07-02T20:16:59.953Z
@DamianoMazza Thanks Damiano,  you are right, apologies for making an incredibly strong claim.
Sasho Nikolov
CC BY-SA 3.0
2014-07-06T08:46:09.670Z
I thank the people for their comments. Here is also an interesting paper,that I found which proves that there are models of set theory, (sets with atoms or Frankel_Mostowski sets) , that when we relax the definition of Turing machines to be over infinite alphabets, and infinite (internal ) states, then Non-determinism does not collapse to determinism in the sense that it holds that P!=NP (P is not equal to NP). http://mimuw.edu.pl/~bojan/papers/atomturing.pdf
Constantine Kyritsis
CC BY-SA 3.0
2014-07-06T08:48:33.770Z
About real life: Since the exponential function, can be approximated by sequences of polynomial functions (e.g. Taylor expansion over all real line in classical mathematics), it is easily realized, that languages of the EXPTIME complexity class. can be approximated arbitrarily well, as far as complexity is concerned (not necessarily PTAS), with sequences of polynomial time decidable languages of P (in spite that P is strictly subclass of EXPTIME). (Comment continuous) –
Constantine Kyritsis
CC BY-SA 3.0
2014-07-06T08:48:52.157Z
(Continues from previous comment) In particular if say within two centuries the 21st, 22nd, the technology of computation ranges, of data sizes, and run-time computation in the interval [n1, n2] (n1,n2 are very large natural numbers), there will always be polynomial time decidable problems of higher complexity-run time, that exponential problems (because there always are polynomials p(n)>2^n on the interval [n1, n2]. Therefore question of the type is NP=EXPTIME or is it P=NP, have less meaning of real situations and more meaning about the behavior of our mathematics at the infinite.
Constantine Kyritsis
CC BY-SA 3.0
2014-07-10T18:05:42.553Z
Set theory and computability do not always play well together. For example, [Goodstein's theorem](http://math.stackexchange.com/questions/3609) is independent of the axioms of Peano Arithmetic. This means there are models of arithmetic where the set of integers with terminating Goodstein sequences is non-computable. Many people would think this set is computable and contains every natural number.
Russell Easterly
<cc.complexity-theory><model-theory>
What is the axiomatic (set theory) context of the P vs NP and NP=EXPTIME conjectures?
Constantine Kyritsis
# What is the axiomatic (set theory) context of the P vs NP and NP=EXPTIME conjectures?

(Asked by: username_0 on 2014-07-01)

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](http://www.claymath.org/sites/default/files/pvsnp.pdf)) 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](http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_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](http://mathpost.asu.edu/~sjgm/issues/2005_spring/SJGM_rogers.pdf))?

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

**Tags:** cc.complexity-theory, model-theory
> **Comments:**
> **username_1**: It is, for any problem in NP, possible to construct a solver S for the problem, such that P=NP implies that S is polynomial.  This makes it unlikely that P=NP is unprovable.  
> **username_2**: 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!  
> **username_3**: You might find this interesting http://www.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.  
> **username_2**: see also [results in TCS independent of ZFC](http://cstheory.stackexchange.com/questions/5934/results-in-theoretical-cs-independent-of-zfc) which indicates roughly "not much so far"...  
> **username_4**: @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_.  
> **username_3**: @DamianoMazza Thanks Damiano,  you are right, apologies for making an incredibly strong claim.  
> **username_0**: I thank the people for their comments. Here is also an interesting paper,that I found which proves that there are models of set theory, (sets with atoms or Frankel_Mostowski sets) , that when we relax the definition of Turing machines to be over infinite alphabets, and infinite (internal ) states, then Non-determinism does not collapse to determinism in the sense that it holds that P!=NP (P is not equal to NP). http://mimuw.edu.pl/~bojan/papers/atomturing.pdf  
> **username_0**: About real life: Since the exponential function, can be approximated by sequences of polynomial functions (e.g. Taylor expansion over all real line in classical mathematics), it is easily realized, that languages of the EXPTIME complexity class. can be approximated arbitrarily well, as far as complexity is concerned (not necessarily PTAS), with sequences of polynomial time decidable languages of P (in spite that P is strictly subclass of EXPTIME). (Comment continuous) –  
> **username_0**: (Continues from previous comment) In particular if say within two centuries the 21st, 22nd, the technology of computation ranges, of data sizes, and run-time computation in the interval [n1, n2] (n1,n2 are very large natural numbers), there will always be polynomial time decidable problems of higher complexity-run time, that exponential problems (because there always are polynomials p(n)>2^n on the interval [n1, n2]. Therefore question of the type is NP=EXPTIME or is it P=NP, have less meaning of real situations and more meaning about the behavior of our mathematics at the infinite.  
> **username_5**: Set theory and computability do not always play well together. For example, [Goodstein's theorem](http://math.stackexchange.com/questions/3609) is independent of the axioms of Peano Arithmetic. This means there are models of arithmetic where the set of integers with terminating Goodstein sequences is non-computable. Many people would think this set is computable and contains every natural number.  

---

## 1 answers

### Answer by username_6 on 2014-07-01. Score: 15

It's not specified. When there is a serious enough candidate paper purporting to resolve P ≟ NP, a Special Advisory Committee will be formed to decide whether (and to whom) to award the prize. I presume that the Special Advisory Committee will decide whether your system of axioms is acceptable. If you assume Z-F with choice, I guarantee you they will take it. If you assume P ≠ NP as an axiom, I guarantee you they won't.

> **Comments:**
> **username_7**: It would be quite interesting/bizarre if choice is required for the proof (i.e. ZFC works, ZF doesn't).  
> **username_0**: I thank the people for their answers so far. It makes sense that it is not specified and it is variable which axiomatic (set theory)  system is assumed. It seems to me that  in a quite restrictive axiomatic set theory (or restrictive model of axiomatic set theory) it is more probable that one can prove that NP=EXPTIME and in a more pluralistic (axiomatic system or model of set theory) more probable that NP is not EXPTIME (finer grades of complexity differences).  
> **username_0**: And even it might happen that one can come with a proof, that inside Peano Arithmetic (with sets definable from logical formulas only without axioms of set theory) the famous conjectures are independent and not provable (Unless there is already a result about these conjectures inside Peano Arithmetic or a simpler impossibility argument which I do not know).  
> **username_0**: And I even dare to say that inside Zermelo-Frankel set theory with axiom of choice , it may be that P=NP or NP=EXPTIME are non-provable and independent. There is an analogy. Polynomial time complexity corresponds to countable infinite N0 and exponential time complexity corresponds to the cardinality of the Power set of the naturals 2^N0. For decades researchers were wondering if there is any other cardinality between them. Goedel (1940) and Cohen (1963) finally proved that both are independent axioms. There is a similar well known proof that corresponds naturalsto ordinals ( Goodstein Theorem)  
> **username_0**: Unfortunately if ones proves the independence of P vs NP conjecture   it seems that he will not be awarded by the Clay mathematical institute 1m , which seems to me unfair  
> **username_6**: @drKCostas: I think that depends on the decision of the Board of Directors of the CMI and any Special Advisory Committee they convene in that case.  
> **username_8**: I think you can safely assume that if you prove (for example) that it's independent of ZFC then they'd pay out, on the same basis that Hilbert's 10th problem is considered solved. In practice the proof of independence might come in two legs (you prove P=NP is consistent and then I prove P!=NP is consistent) and then they have to make a call. Or you might prove that it's independent of Peano but not know whether AC resolves it, then Peter proves AC implies P=NP. Again you're at their mercy but don't worry, do that and the CS community will find you a job!  
> **username_0**: Well said! I admit, I had forwarded a week ago to Stephen Cook, and the president of the Clay mathematical institute, an email that was suggesting to modify the awarded  conjecture, from 2 cases P=NP, P!=NP to 3 cases, the third being that someone proved that both P=NP, P!=NP are independent in ZFC. To be more precise, I was suggesting to Scott Aaronson to requested this modification, as he was the author of the paper here http://www.scottaaronson.com/papers/pnp.pdf  
> **username_9**: No one seriously thinks that P != NP is independent of ZFC. We don't know of any non-contrived mathematical statements that are independent of ZFC (other than the obvious Godelian ones). This outcome just isn't going to happen.  
> **username_0**: @David Harris I think I just mentioned above, the continuum hypothesis which is a natural statement in ZFC, which has been proved independent. Even in Peano arithmetic, there is a natural statement (Goodstein theorem in ZFC see http://en.wikipedia.org/wiki/Goodstein's_theorem) which is independent in Peano.  
> **username_10**: @usul: It's not just bizarre, it is in fact impossible. ZFC is conservative over ZF for arithmetical statements.  

---

