Mike O'Donnell tells a story of talk he saw once where the speaker considered the following recursive program: `f(n) := output 0 if n = 0; output f(n-1) otherwise.`

Suppose we could prove P≠NP in the theory of arithmetic. I can create a machine M that solve SAT on standard formula φ using |φ|

^{k}time if k is nonstandard: Since k and thus |φ|^{k}is greater than every standard integer, we have time to do exhaustive search. However there will be some nonstandard φ that M will fail to solve satisfiability in time |φ|^{k}time, for whatever the satisfiability question for nonstandard φ means.Now suppose P=NP in the standard model but P≠NP in some non-standard model (and thus the P versus NP question is independent of the theory of arithmetic). We have a standard machine M and a standard integer k such that M(φ) correct computes whether a standard φ is in SAT in |φ|

^{k}steps. But for some non-standard φ, M(&phi); would fail even though it gets to run in time n^{k}for the nonstandard n=|φ|. Even if we allow M and k to be non-standard there will be some φ that M will fail to determine satsifiability.You can keep playing this game and never get into trouble assuming the theory of arithmetic is consistent. But I get a headache when I try to think what non-standard Turing maching, non-standard polynomial running time and satisfiability of non-standard formula really mean.

--

Posted by Lance to Computational Complexity at 3/29/2005 08:37:00 PM