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?
Best Answer
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.