Limit, logic, and computation
-
Contributed by Michael H. Freedman
Abstract
We introduce “ultrafilter limits” into the classical Turing model of computation and develop a paradigm for interpreting the problem of distinguishing the class P from NP as a logical problem of decidability. We use P(NP) to denote decision problems which can be solved on a (nondeterministic) Turing machine in polynomial time. The concept is that in an appropriate limit it may be possible to prove that problems in P are still decidable, so a problem whose limit is undecidable would be established as lying outside of P.
Footnotes
-
↵ * Convergent can be taken to mean that there is a pointed metric space (Y, y 0), so that for every radius r there exists an ɛ > 0, so that the ball of radius r about id in G ɛ, (B r(id ⊂ G ɛ), id) imbeds into (Y, y 0) (1 + 1/r)-quasi-isometrically (i.e., with metric distortion between factors of (1 + 1/r) and (1 − 1/r)), and that every point of Y is in the closure of the images of these balls.
-
↵ † The function f̄ is efficient in the sense that from any initial point f(i 0), the sequence f(i 0), . . . , f(i 0 + c n r n) will completely explore the ball of radius r in Z n about f(i 0) for some constant c n depending only on the dimension n.
-
↵ ‡ Perhaps “decidable” should be replaced here with some notion “continuously decidable” as discrete proofs limit to continuous objects.
-
↵ § This denotes the standard axiomatization of arithmetic which features the rules for addition, multiplication, and mathematical induction.
- Copyright © 1998, The National Academy of Sciences
