Independence of P = NP?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

---

Edit (addition to address comments at top of thread):

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.

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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.

See: http://www.scottaaronson.com/papers/pnp.pdf

Answer 8

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.