# Independence of P = NP?

Let's suppose P = NP is independent (of ZFC). Then there is a model of ZFC in which there is a polynomial time algorithm for SAT. But suppose this algorithm is correct, wouldn't this algorithm exist in the standard model? In the end an algorithm is a number. My question is: How can it be that there exists a polynomial time algorithm for SAT in a model of ZFC and yet P = NP is unprovable? In other words, how can P = NP be independent?

-
Zirui: It is my impression from what you write that you do not understand well the difference between sets and their representation in models of set theory. If your model is not an $\omega$-model, (meaning, if its version of the natural numbers is not isomorphic to the true natural numbers), I am not sure I understand what you mean by "the algorithm is correct", unless you mean that the algorithm exists in $V$ (so P=NP), and the model is correct about the algorithm being polynomial time and solving SAT. Why don't you begin by explaining this part better? – Andrés Caicedo Dec 21 '10 at 4:03
@Zirui: Your confusion in this question is the same as your earlier question regarding CH: mathoverflow.net/questions/28806/… Andres' comment and Jason's answer below, for instance, both echo the very thoughtful answer JDH gave you earlier. Things said then about a counterexample to CH in a model apply mutatis mutandis to algorithms in a model witnessing P=NP. So in addition to digesting what's here, it might pay to revisit the answers to that earlier question. – Ed Dean Dec 21 '10 at 7:15
If you ask a question that confuses holding in a model with being true, then MathOverflow tries to explain the difference. A pointed observation, that is. Not even hints would help. – Ricky Demer Dec 21 '10 at 9:46
unable to parse: [[good enough to prove P = NP] in this model] or [good enough to prove [P = NP in this model]] – Ricky Demer Dec 21 '10 at 10:06
I strongly recommend that people reading here take a quick trip through Zirui Wang's previous questions -- they have a characteristic flavor, and it's good to know what you're getting in to. – JBL Dec 21 '10 at 14:26

There are examples such as the one due to Levin mentioned here which you can write down explicitly, but whose running time is polynomial if and only if P=NP. Thus in some [admittedly rather trivial] sense it's not finding an algorithm which is hard, but proving that it runs in polynomial time. This is the part which could conceivably be independent.

-
This algorithm is not even recursive, meaning it halts on all inputs. A polynomial time algorithm must be recursive in the first place. – Zirui Wang Dec 21 '10 at 5:12
A minor clarification: Levin-type algorithms (which can approximately describe as just running all possible algorithm in parallel) rely on a sub-algorithm producing a polynomial size certificate that can be verified polynomial time. Thus it gives an explicit polynomial time algorithm for NP \cap CoNP (if and only if NP \cap CoNP = P) but not for all of NP. – Mark Lewko Dec 21 '10 at 5:51
@Zirui: This is easily fixed by running any old (not necessarily polytime) algorithm in parallel with the rest and returning the result of that if it completes. – Noah Stein Dec 21 '10 at 15:31
@Mark: Wow, good point. I had somehow failed to notice that. Thanks! – Noah Stein Dec 21 '10 at 15:32
Suppose P = NP. Then this algorithm has a polynomial upper bound. But you may not be able to tell this bound in advance. So it still does not prove the algorithm is polynomial time. It boils down to the definition of polynomial time. In fact it may take infinite time to find the bound. – Zirui Wang Dec 23 '10 at 12:28

I think the following is implicit in earlier answers, but let me state it briefly. I'm addressing only the original question, not CH or other matters that gradually entered this discussion.

The main point is that a model of ZFC can have non-standard natural numbers; they're larger than all the standard ones, so we sometimes call them "infinite" even though from the point of view of the model they're finite. (That is, they satisfy, in the model, the formula that defines "finite ordinal number".) Now suppose such a model satisfies "There is PTime algorithm for SAT." Fix such an algorithm in the model, say a Turing machine program. It is true in the model that this algorithm has a finite number of control states (because that's part of the definition of "Turing machine") and that its running time is bounded by a polynomial, of some finite degree, of the input length (because that's part of the definition of "PTime"). Unfortunately, both of the occurrences of "finite" in the preceding sentence are (like the whole sentence) to be understood in the sense of the model. Neither the number of states nor the degree of the polynomial will necessarily be an actual natural number (in the sense of the real world rather than the model); they can be non-standard numbers. So the model's Turing machine might not be an actual Turing machine, and, even if it is, its running time might not be bounded by an actual polynomial.

-
Excellent answer! But I think your definition of "finite", which is relative, is not what computer scientists have in mind. Can you refute this? This nonstandard number does not have the exactness property that natural numbers have and hence it does not correspond to the Godel encoding of a Turing machine. – Zirui Wang Dec 22 '10 at 12:55
I was just reading a paper "communicated by Andreas R. Blass" and then I saw this answer by Andreas Blass. I said "Wow!" – Zirui Wang Dec 22 '10 at 13:01
@Zirui Wang: I'm not sure what you mean by "exactness property," but indeed a nonstandard number would not be the Gödel encoding of a Turing Machine in the real world. It might nevertheless be such an encoding in the model; i.e., it might satisfy, in the model, the formula expressing "Gödel encoding of a Turing machine," and that is why it might (if it satisfies appropriate additional formulas about computing SAT and taking only polynomial time) witness the truth of P=NP in the model, without witnessing P=NP in the real world. – Andreas Blass Dec 22 '10 at 16:11

This answer is basically an elaboration of Jason's answer, but it's too big to be a comment.

It's a little hard to speculate on a proof that doesn't exist, but most likely if someone constructed a model of ZFC where P=NP, then the "algorithm" in the model wouldn't be a real algorithm. You can formalize the notion of algorithm in first-order logic over the natural numbers, but the formalization is incomplete in the sense that there will be non-standard models that satisfy the same axioms. It's possible that someone will write down a model of ZFC where the set of natural numbers is "too big" — it contains natural numbers other than $0, 1, 2, 3, \ldots$ — such that for "algorithms" defined using these non-natural natural numbers, P=NP.

For example, the "algorithms" in the model could correspond to algorithms where you can take infinitely many steps. A non-standard natural number (by necessity) must be strictly bigger than every standard natural number, so Turing machines in this model would have extra states at infinity. Since time itself is a natural number, the running time of algorithms can take on infinite values. So now you have algorithms that have infinite steps, and can take infinitely long to run. From this, we can't learn much about whether P=NP in the real world.

I know this is all counterintuitive, but the reason is that once you are cooking up a model of ZFC, the only thing you have to do is formally satisfy the axioms, and the axioms don't constrain you enough to prevent you from creating non-standard models. If you want to understand this better, I suggest reading up on Skolem's construction of non-standard models of the natural numbers over Peano Arithmetic.

-

Let me ask you a question instead. The consistency of PA is known to be independent of PA so we have a model of PA that thinks there is a proof of something contradictory like $0 \neq 0$. Therefore, this "proof" that $0 \neq 0$ is in the set-theoretic universe $V$. So does $V$ think that Peano Arithmetic is inconsistent?

The answer is no because $V$ realizes that this is not a true proof but rather a proof involving nonstandard numbers either with formulas or length. The same type of idea is happening here. Even if we have a nonstandard model thinking that it has a polynomial time algorithm for SAT, a standard model looking at this algorithm may see things differently. For an even more extreme example, consider the fact that if we take a total computable function $f$ with any given running time, a nonstandard model computes the standard portion of it in a time amount that it views as constant because it has a fixed $c$ that's greater than every Natural number. But does this mean that the function can actually be computed in constant time? Of course not, because $c$ is not a true finite number.

I should also make mention that the last thing I said is of a slightly different nature since even the nonstandard model will not view itself as computing the function in constant time. Mainly, it does not know where the standard portion ends and the nonstandard part begins.

If P = NP turned out to be independent of ZFC, then we'd have a model of ZFC that would think that P = NP since by the definition of independence, P $\neq$ NP would not be provable from the axioms of ZFC. However, this would not be sufficient for generalizing the result to all models as you conjectured since there would also have to be a model of ZFC thinking that P $\neq$ NP by virtue of ZFC not proving P = NP. These results follow directly from Gödel's completeness theorem. On the other hand, if P = NP were provable in ZFC, then all models of ZFC would think that P = NP.

-
Who says Con(PA) is independent of PA? Godel's second incompleteness theorem only asserts Con(PA) is not provable. ~Con(PA) might be provable in PA. – Zirui Wang Dec 21 '10 at 5:08
If Con(PA) is not provable from PA, then PA is consistent because if a theory is inconsistent, then every statement is provable from that theory. – Jason Dec 21 '10 at 5:11
Godel's second incompleteness theorem assumes Con(PA). It states: If Con(PA), then Con(PA) is not provable. – Zirui Wang Dec 21 '10 at 5:18
Let me restate what I'm saying because you're right, the logic would be circular with this assumption. If PA is not consistent, then every statement is provable in PA. This is because everything follows from a contradiction. So if this were the case, then we'd have a proof of both CON(PA) and ~CON(PA). And I guess technically then CON(PA) would not be independent of ZFC, but then we'd also have a proof of both P = NP and P $\neq$ NP and no set-theoretic universe. – Jason Dec 21 '10 at 5:36
We discussed this issue over at math.SE, maybe reading math.stackexchange.com/questions/5377 would help you. – David Speyer Dec 21 '10 at 13:34

I think the source of the confusion here is the idea that all models of ZFC have the same notion of what a "natural number" (and hence, by an appropriate encoding, an "algorithm") is. Unfortunately, Godel's incompleteness theorem tells us that no recursively enumerable axiom system (of which ZFC is an example) can precisely pin down the theory of the true natural numbers (i.e. true arithmetic), which can thus only be fully described in the metatheory rather than in any formal system. As such, there exist statements G about natural numbers which are true in some models of ZFC and false in others, because these two models have genuinely different interpretations of the natural number system.

It is a proiri conceivable (though, in my opinion, unlikely), that P=NP is one of these statements. Specifically, it is conceivable that SAT is not solvable in polynomial time in the standard model of the natural numbers, but is solvable in polynomial time in an exotic model of the natural numbers, even if both models of the natural numbers are part of respective models of set theory obeying ZFC. The point here is that the exotic algorithm could have a length which is an exotic natural number, which could be larger than every standard natural number; similarly, the constants in the polynomial run time for this exotic algorithm could also be larger than every standard number. So there is no obvious way to convert the exotic polynomial time SAT solver into a standardly polynomial time SAT solver; it may even be that the exotic algorithm cannot be described at all in the standard model, let alone have a polynomial run time.

[Edit: actually, with Levin's trick, if SAT is solvable, it is always solvable with a bounded-length algorithm (namely, "run all possible algorithms in parallel in a carefully chosen manner"), so exotic length is not a genuine issue. However, this still does not exclude the possibility of exotic run time constants.]

It is even conceivable (though, again, I believe it to be unlikely) that the reverse is true: SAT is solvable in polynomial time in the standard model, but not in a exotic model. Here, the standard algorithm has a length which is a standard natural number, so the algorithm can at least be described in the exotic world. But just because it has a polynomial run time in the standard model, this does not necessarily imply a polynomial run time in the exotic model (unless one has a transfer principle, as is the case in the models coming from nonstandard analysis, but not all exotic models are of this type); the algorithm may solve all standard SAT problems in a polynomial amount of time, but require super-polynomial time to solve an exotic SAT problem. [In this scenario, ZFC + P!=NP would be $\omega$-inconsistent, but could still be consistent.]

-
It could also be that not all instances of SAT are in the universe. – Zirui Wang Apr 14 '11 at 17:28

This answer started life as a nascent comment intended for the back-and-forth above, but it ballooned into what follows.

ZW, as I pointed out above, your current question does parallel your earlier question about CH, as do the (very good) answers in each case. From your further comments, though, I think I now have some idea why the answers haven't satisfied you; I'll take a stab at answering what I think's bothering you. (If I'm right, then it's a fairly simple matter, but just one that wouldn't be the initial guess as the issue on MO. And if I'm wrong about what you don't like, oh well; but I've genuinely tried to figure out why you're unhappy with the answers so far given.)

The answers given try to clarify a (very common and understandable) mathematical confusion that people can have about independence results, but your further comment:

My confusion is, people take V as the standard model. But why so?

suggests something else is at the heart of what's bothering you personally. And now looking at your original question about $CH$, it seems clear there as well:

OK, Cohen has constructed a model in which both ZFC and ~CH are true. Isn't this model an answer to the continuum problem? Hasn't he showed that it is indeed possible to construct a set with cardinality between that of the integers and that of the reals? Why is it still not considered sufficient to settle CH? Why is one model not enough? Why for all models? In other words, why do we have to answer whether "ZFC |- CH" instead of just "CH" itself?

So it seems that part of what you're not happy with is simply the (extra-mathematical, somewhat conventional) privileged position of $ZFC$ as a foundational theory for mathematics. (Again, if I'm wrong in ascribing such thoughts to you, my apologies.) And that's perfectly fair; plenty of people have taken issue with that status for myriad reasons.

So maybe you're really thinking: "Hey, Cohen constructed this model $\mathcal{M}\models ZFC + \neg CH$, and I think this $\mathcal{M}$ can be (or should be, or is) the mathematical universe we all work in." Well that's a perfectly acceptable way to think, but now you no longer have a purely mathematical pursuit on your hands (one reason, by the way, why myself and others generally would be expecting to answer the question the way they did), thanks to the privileged position $ZFC$ enjoys. Now you've also got a sociological (and dare I say philosophical) endeavor, namely that of convincing fellow mathematicians of the truth/efficacy/beauty/... of your favored universe.

Those who answered you were working under the accepted convention that "settling" a problem means either proving it in $ZFC$, or refuting it there, or establishing its independence from $ZFC$, and answered your initial queries accordingly (and accurately). If I'm right about what you're finding unsatisfactory here, then you now get to immerse yourself in the delights of the philosophy of mathematics. Enjoy! (And if I'm wrong, at least I've only wasted my own time.)

-
Why do you consider a model in which ZFC hold outside the universe in which mathematicians work? (Model theory.) – Zirui Wang Dec 21 '10 at 11:34
I don't. My point is only that any statement which "merely" holds in some particular model of ZFC, rather than all of them, holds a less privileged pedigree than statements which hold in all of them (i.e. are provable in ZFC). Most non-logician mathematicians don't give much thought to foundations, nor do they need to. If you demanded an answer as to their foundations, they'll most likely say something like ZFC (and hope you go away :). If you point at a model of ZFC + -CH and argue that settles CH in the negative, anyone can point at a model of ZFC + CH and say "What about that?" .... – Ed Dean Dec 21 '10 at 11:48
As long as ZFC is the arbiter of such matters, there's nothing more to say than CH is independent of our axioms. So if you want to make a definite case one way or the other, you're asking people to change what is currently a pretty well entrenched convention. You'd need to offer some good reasons, of some sort or another. I recommend looking up "intrinsic" and "extrinsic" justification of axioms in relation to Godel, and perhaps some of the writings of Peter Koellner if you're interested in such matters. – Ed Dean Dec 21 '10 at 11:53
What more that can be said is that CH is 'more canonical' than -CH, because (I remember reading somewhere that) you can go from either to the other by forcing extensions, while minimal models satisfy CH. – Ricky Demer Dec 21 '10 at 11:56
Sure, you can say that CH is "more canonical" in some sense, or you can, say, argue for -CH along the lines of Koellner, working from a network of results by Woodin. In each of these cases, you are no longer letting ZFC and what it proves be the sole arbiter. All I wrote before is that " As long as ZFC is the arbiter of such matters, there's nothing more to say ..." – Ed Dean Dec 21 '10 at 12:05

As an addition to arsmath's answer, to make it clearer how these "additional" numbers may look like:

Lets say you have defined the class of ordinals $\mathbb{O}$, the successor-functor $S$, and the set of finite ordinals ("naturals") $\omega$. Then $a < b$ can be defined by $a\in b$ for $a,b\in\mathbb{O}$. Now you can create the formulas $A_0=n\in\omega\wedge n>\emptyset$, $A_1=n\in\omega\wedge n>S\emptyset$, $A_2=n\in\omega\wedge n>SS\emptyset$, ..., i.e. $A_i$ states that that there is a natural number $n$ that is larger than $i$.

Trivially, $ZFC\models A_i$. Hence, assuming $ZFC$ was consistent, by the Compactness Theorem, also $ZFC\cup \{ A_i|i\in\omega \}$ is consistent, and has a model. In this model, there is a number $n$ of which the model "thinks" it was finite (since it is in the $\omega$ of this model), which is not in "our" $\omega$ of the metatheory, since all the $A_i$ force this additional element to be larger than everything we consider finite.

Especially, there may be algorithms that - if they even make sense - will not terminate in "finitely" many steps, since this model has another understanding of finity. Since $X^n$ for this $n$ would be a polynomial for this model, such an algorithm could as well be in $P$ for this model.

-

This doesn't seem like much of a research-level question or discussion, but anyway I'm surprised to see no mention of Scott Aaronson's article: "Is P Versus NP Formally Independent?". It explains a lot of these basic issues in logic and would probably be helpful.

-