Tuesday, March 29, 2005

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.
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.


  1. Actually, doesn't the original example break down? It was my understanding that nonstandard numbers were like ordinals in that "n-1" is not necessarily well-defined, and that they can have no infinite decreasing subsequence? So any well-defined program following that outline would still have to terminate in a finite number of steps.

    But, maybe I'm applying set theory inappropriately here, so I could be wrong...

  2. There is a paper in
    JACM by Attila Mate (vol. 37, no 1, 1990) followed by a paper in TCS (I don't remember the author). Together they give a necessary and sufficient for NP not to be equal to coNP in terms of nonstandard models of Peano arithmetics.

    Gabriel Istrate

  3. Even if n is nonstandard, n-1 is always defined (unless n=0). Every countable nonstandard model of PA is order isomorphic to N + Q*Z, where Q*Z is the lexicographic
    order of pairs (q,n) where q is rational and n is in Z. Hence there are infinite descending sequences if you're looking at the model from the "outside," but of course any nonempty subset that's *definable* in the language of arithmetic will have a least element.

    By the way, if someone uses the term "theory of arithmetic" then they typically mean the set of all first-order sentences that are true in the standard model, and it doesn't really make sense to say that P=NP is independent of the theory of arithmetic in this sense. The intended term was probably "PA" or first-order Peano arithmetic.