[Computational Complexity] A Non-Standard Post
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 nk 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