Does the independence of P = NP imply existence of arbitrarily good super-polynomial upper bound for SAT? - MathOverflow

Does the independence of P = NP imply existence of arbitrarily good super-polynomial upper bound for SAT?

2010-06-12T18:40:48Z

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) > x^k.

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) = x^k 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?

Answer by T. for Does the independence of P = NP imply existence of arbitrarily good super-polynomial upper bound for SAT?

2010-06-12T19:53:50Z

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.

Answer by JBL for Does the independence of P = NP imply existence of arbitrarily good super-polynomial upper bound for SAT?

2010-06-26T22:08:48Z

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: http://mathoverflow.net/questions/21616/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.