9

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

Juho
  • 3,170
  • 2
  • 26
  • 36
Constantine Kyritsis
  • 183
  • 6
  • 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 Jul 01 '14 at 14:19
  • 1
    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 01 '14 at 15:23
  • 1
    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 Jul 01 '14 at 23:27
  • 1
    see also results in TCS independent of ZFC which indicates roughly "not much so far"... – vzn Jul 02 '14 at 01:44
  • 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. – Damiano Mazza Jul 02 '14 at 14:06
  • 1
    @DamianoMazza Thanks Damiano, you are right, apologies for making an incredibly strong claim. – Sasho Nikolov Jul 02 '14 at 20:16
  • 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 Jul 06 '14 at 08:46
  • 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 Jul 06 '14 at 08:48
  • (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 Jul 06 '14 at 08:48
  • Set theory and computability do not always play well together. For example, Goodstein's theorem 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 Jul 10 '14 at 18:05

1 Answers1

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.

Peter Shor
  • 24,763
  • 4
  • 93
  • 133
  • 1
    It would be quite interesting/bizarre if choice is required for the proof (i.e. ZFC works, ZF doesn't). – usul Jul 01 '14 at 13:55
  • 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 Jul 01 '14 at 15:14
  • 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 Jul 01 '14 at 15:15
  • 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 Jul 01 '14 at 15:47
  • 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 Jul 01 '14 at 15:50
  • @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 Jul 01 '14 at 16:01
  • 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 Jul 01 '14 at 19:01
  • 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 Jul 02 '14 at 18:53
  • 3
    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 Jul 03 '14 at 19:43
  • @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 Jul 06 '14 at 08:09
  • 3
    @usul: It's not just bizarre, it is in fact impossible. ZFC is conservative over ZF for arithmetical statements. – Emil Jeřábek Jul 10 '14 at 08:41