## [Computational Complexity] A Non-Standard Post

Expand Messages
• 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)
Message 1 of 1 , Mar 29, 2005
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. ```
By straightforward induction one can show that for any natural number n, f(n) will halt in a finite number of steps. The speaker argued that if we take n to be a non-standard natural number (which is bigger than all the standard integers) than the program will never halt. Mike O'Donnell counters that it will halt, just in a non-standard number of steps.

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

Your message has been successfully submitted and would be delivered to recipients shortly.