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

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.

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

There is a paper in

ReplyDeleteJACM 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

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

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