Let me first define what "super-polynomial" means.

Definition. We call a function f super-polynomial if for all k, there exists a constant n such that for all x ≥ n, f(x) > xk.

Now please judge whether the following claim is true.

Claim. Suppose P = NP is independent of ZFC. Then for any super-polynomial function f, there exists an algorithm for SAT whose worst case running time is bounded by f.

OK. To help your judgement, I will give you my proof of the claim. Of course it may be wrong or missing something.

Proof. Proof by contradiction. Suppose that there is no such SAT algorithm. Then all algorithms for SAT are not bounded by f. Note that f is not bounded by any polynomial function of the form g(x) = xk for some k. Therefore no SAT algorithm is bounded by a polynomial. This means SAT ∉ P and hence P ≠ NP. We have just shown that P ≠ NP is provable, contradicting with our assumption that P = NP is independent. QED

If my proof is correct, isn't this claim too obvious? OK, but why there are still people publishing weaker claims, for example the main result of this paper? Did I misinterpret their result? Is it actually stronger than my claim?

Also, this claim is an example for the strength of the independence of P = NP. If it's indeed independent, then all statements that imply P = NP are false and all statements that imply P ≠ NP are also false. An example of the former is "There exists a polynomial time SAT solver." Since this is false, then there does not exist any polynomial time SAT solver. And the latter implies whatever super-polynomial time bound you give, there is a SAT solver with this bound. So if independence is true, then the picture is that there is an infinite sequence of (SAT solver, time bound) pairs, with each bound faster than the previous, approaching the limit of P. And yet, it never crosses the boundary. So if independence is true, we can expect to improve the time bound for SAT endlessly in the region of super-polynomial and yet never reach P. Now I hope you have a clearer picture of the possibility that P = NP is independent.

Sorry for the digression, but first of all, is the claim true?

  • $\begingroup$ Wait, does independence imply "There exists a polynomial time SAT solver" is false? Or does it just imply "One cannot prove using ZFC that a SAT solver is in fact polynomial"? $\endgroup$ – Dror Speiser Jun 12 '10 at 18:56
  • $\begingroup$ So we may have a polynomial time SAT solver but we can't prove a polynomial bound. So complexity study is inherently inferior to algorithm design, because proof is subject to axiomatics? As Richard Karp says in a recent lecture, now he is not ashamed of giving practically fast algorithms without caring about polynomial time bounds. $\endgroup$ – Zirui Wang Jun 12 '10 at 20:15
  • $\begingroup$ "If it's indeed independent, then all statements that imply P = NP are false and all statements that imply P ≠ NP are also false". This sentence is clearly wrong. The statement "P = NP" certainly implies itself, and the assumption is that it is independent of ZFC, not false. I agree with the statement if you replace "false" by "not provable from ZFC"; then it is simply a tautology. $\endgroup$ – Theo Johnson-Freyd Jun 12 '10 at 22:01
  • $\begingroup$ Junbin Teng would yell "Brute force! Brute force!" $\endgroup$ – Zirui Wang Jun 12 '10 at 23:16
  • 1
    $\begingroup$ @ZW: there is no well-defined concept of what it means for an infinitary statement to be "true" without further comment (i.e., without reference to any specific formal system where the statement is a theorem). When discussing independence there are always at least TWO formal systems involved: one system that proves the statement and another that does not, so one has to be more explicit. Also, if ZFC does not prove P < NP, it does not follow that P < NP, because (a) P=NP is not a directly falsifiable $\forall n f(n)$, statement, and (b) a reasonable stronger theory might prove P<NP. $\endgroup$ – T.. Jun 14 '10 at 21:24

Zirui Wang, if I understand your proof correctly, then it is wrong.

You've made the supposition "No SAT algorithm is bounded by $f$" (where $f$ is some super-polynomial function). From this is certainly follows that no SAT algorithm runs in polynomial time; however, it does not follow that this latter statement is provable (in ZFC or whatever). You've substituted the a priori knowledge that $f$ has the desired property for a proof that $f$ has the desired property, but it's the latter of these two that you actually need to make your argument work.

(The same sort of error was made, I believe, in the fallacious argument here: Provability of termination. Whats wrong with my reasoning? )

Similarly, the claim "If it's indeed independent, then all statements that imply P = NP are false and all statements that imply P ≠ NP are also false," is wrong -- if P = NP is independent, then all statements implying P = NP are either false or unprovable.

| cite | improve this answer | |
  • $\begingroup$ Further, this is the same mistake you've made in at least one other post, e.g., here: mathoverflow.net/questions/28110/is-zfc-inconsistent-closed From the assumed truth of a statement, the provability of that statement emphatically does not follow. $\endgroup$ – JBL Jun 26 '10 at 22:59
  • $\begingroup$ @JBL: Thank you but why it doesn't follow? My reasoning is like this: Suppose P is true. Then {} -> P is true. And therefore ZFC -> P is true. To me truth is a very strong statement. If we know something is true, then there is no need for proof. It's true! Of course how we know it is a problem. $\endgroup$ – Zirui Wang Nov 30 '10 at 10:02
  • 1
    $\begingroup$ @Zirui Wang, you write, "Suppose P is true. Then {} -> P is true." This is wrong if "$\to$" means "is enough to prove." The statements "P is provable" and "P is true" are different statements, and in particular they are not logically equivalent (notably the second does not imply the first). You keep trying to substitute the latter for the former, but this is not valid. $\endgroup$ – JBL Dec 1 '10 at 13:48

Suppose that a stronger theory, such as Zermelo Fraenkel set theory (ZF), proves that P < NP, but another weaker theory, such as Peano Arithmetic (PA), cannot prove it (so the independence of P=NP is understood relative to the latter).

Then the independence proof might work by showing that arbitrarily PA-good superpolynomial upper bounds exist (ones where the superpolynomial growth function is provably total in PA), so that PA can't tell the difference between the true bounds and polynomial ones.

However, the proof of P < NP in ZF would construct a specific superpolynomial lower bound, so one could not get closer to polynomial than that function. ZF can construct (prove existence of) functions that are superpolynomial but increase more slowly than anything PA can construct.

Obviously the same discussion can hold for any base theory in place of PA.

| cite | improve this answer | |
  • $\begingroup$ You mean the class of all possible functions is subject to the theory we are using? But we normally don't talk about the theory when referring to all possible functions, do we? $\endgroup$ – Zirui Wang Jun 12 '10 at 20:26
  • $\begingroup$ Independence always involves multiple theories, so you have to specify. A theory can't prove a statement independent from itself, as this would establish its own consistency. For independence there is always a stronger theory proving that a statement can't be proved in a weaker one. Sometimes the stronger theory isn't specified clearly, because many different ones would work. $\endgroup$ – T.. Jun 12 '10 at 20:49
  • $\begingroup$ @Zirui Wang: Yes, that's correct. Any given theory cannot really know about all functions. For one illustration, there are famous models of "nonstandard analysis" (constructed by ultrafilters) that have strictly more functions (and strictly more numbers!) than "standard" analysis. But language/theory of "real analysis" is satisfies by NSA. So perhaps the real world is actually one of these larger non-standard models, and there are real functions that the language cannot see. You have no way of knowing. $\endgroup$ – Theo Johnson-Freyd Jun 12 '10 at 22:06
  • $\begingroup$ @T.: Can you explain why "a theory can't prove a statement independent of itself, as this would establish its own consistency"? Also if what you said is true, then what theory is used to prove "CH is independent of ZFC"? $\endgroup$ – Zirui Wang Jun 15 '10 at 3:33
  • 2
    $\begingroup$ An inconsistent theory proves every statement. Showing that a specific statement can't be proved in the theory also shows that the theory is consistent. Goedel and (I think) Cohen used ZF+Con(ZF) as the theory in which to construct models of ZF+CH and ZF+not(CH) respectively. $\endgroup$ – T.. Jun 15 '10 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.