Since the P/NP problem has at its core the distinction between polynomial and exponential growth, it is natural to look for perspective to other models within mathematics where this dichotomy is manifest. In complex analysis an exponential function, e.g., 2^z, has an essential singularity at infinity, in contrast to the continuous branched structure at infinity exhibited by a polynomial. This dichotomy is mirrored in cardinal arithmetic (1) where the function 2^x is discontinuous at every limit cardinal α, for which no smaller cardinal β has a power set P(β) equinumerous with P(α), that is,

The theory of group presentations may be taken as an analog of computation. Milnor (3) and Schwarzc (4) introduced the notion of the growth of a finitely generated group G. The group G has polynomial growth (exponential growth), if it has a presentation in which the number of distinct elements of G which can be written as words of length = in the generators and their inverses is ≤P() for some polynomial P (≥b for some base b > 1). It is easy to show that both these properties are in fact independent of the presentation and depend only on the group G.

Within this theory we will explain how taking the appropriate limit transforms a distinction in growth rates into a dimensional dichotomy. A celebrated theorem of Gromov’s (5) states that G has polynomial growth iff it contains a nilpotent subgroup of finite index. The proof considers a sequence of base-pointed metric spaces {(G, id)}, → 0, where G has metric dist(g₁, g₂) = (minimum word length (g₁g₂⁻¹)). This sequence has a convergent subsequence, in the Gromov-Hausdorff sense, if and only if G has polynomial growth, in which case the limiting metric space (Y, y₀) is finite-dimensional.* The proof proceeds by representing G into isometries (Y), which is a Lie group by the Montgomery-Zippen theorem. Ultimately, the limit Y is seen to be a nilpotent Lie group endowed with a Carno-metric. For example, if G = integers Z, then Y is the real line R. If G = Zⁿ, then Y = Rⁿ. If G is the discrete Heisenberg group

If G has faster than polynomial growth, {G, id} will not approach a limit in the Gromov-Hausdorff sense, but an ultrafilter limit can be forcibly extracted. Let (X_i, _i) be any sequence of pointed metric spaces i = 1, 2, 3, . . . . Consider admissible sequences {x_i X|, there exists a constant c so that dist(_i, x_i) < ic. Let ω be any non-principle ultrafilter in Ž⁺, i.e., ω belongs to the growth Ž⁺Z⁺ in the Stone-Cěch compactification Ž⁺ of Z⁺. Using the universal property

If the sequence ((X_i, dist_i), _i) is convergent in the Gromov-Hausdorff sense, then this limit is also the ω-limit; however, the ω-limit exists in complete generality. For example, when applied to the constant sequence {G, id}, G a word-hyperbolic group (the generic case for groups of nonpolynomial growth; ref. 6), then the ω-limit is an -tree (a space in which there is a unique imbedded interval joining every two points). Although of covering dimension one, this -tree is enormously large, in the sense that there is no countable basis for its topology and its Hausdorff dimension is infinite.

The paradigm: “polynomial growth implies a well-behaved limit,” if applied to the P/NP problem, would take the schematic following form:

Applications of Paradigm There is a toy model of computation, the search of a database, in which this paradigm applies. Consider the databases consisting of the positive orthant of Zⁿ and W, where Zⁿ is the integer lattice in Euclidean n-space and W is the universal unrooted 3-valent tree with edges of length = 1. (W could also be taken to be a co-compact lattice in any hyperbolic space Hⁿ, n ≥ 2, and all the following assertions would remain true but be slightly more technical to check.) Writing each integer r Z in base 2, the kth component f_k(r) of a map f:Z⁺ 0 → Zⁿ is defined by reading only the digits congruent to k mod n. Now fix any non-principle ultrafilter ω Ž⁺. Regarding Z⁺ 0 as a sequence of spaces where the jth copy has its standard metric multiplied by (j)⁻⁽ⁿ⁻¹⁾, and regarding Zⁿ as the constant sequence of spaces, a Hölder-1/n continuous ω-limit :R⁺ 0 → Rⁿ is obtained from applying the limit construction to domain and range simultaneously. The map f may be interpreted as a particularly efficient† search of the positive orthant of Zⁿ; the rescaling of Z amounts to a speed-up of the search, so that the ball of radius j in the jth Zⁿ is searched in time proportional to j. Finally, is the limiting solution to the infinitary version of the search problem in which all points in the positive orthant of Rⁿ must be visited. The map is the Peano-Hilbert curve.

Turn now to ω-limit (W, w₀) where some vertex of W has been chosen as basepoint. There are 2^₀ edge paths leaving w₀ and heading toward infinity. These define an uncountable set of sequences {w_i,j}, i Z⁺, j 2^₀, whose mutual ω-distances d({w_i,j}, j, {w_i,j′}) = 2 are all two. This implies that the ω-limit W = has no countable basis for its topology. Consequently, is not equal to the image under any continuous map of any second countable space, e.g., R⁺ 0. Thus no discrete search of W can be constructed so that a rescaled limit leads to a continuous search (i.e., epimorphism) of . In these models we see “polynomial time” converging to continuous and “exponential time,” failing to define an appropriate limit, echoing the observations in complex analysis and cardinal arithmetic.

Let N_k be the set of Boolean formulae which are conjuctions of k-fold disjuncts of a finite alphabet of literals; k-sat denotes the satisfaction problem for fomuli in N_k. It is well known (7) that 2-sat lies in P, whereas 3-sat is NP-complete. In “k-sat on Groups and Undecidability” (unpublished work), an infinitary version of k-sat is introduced which depends on a fixed infinite group. Truth assignments for group elements are sought subject to a family of disjunctive clauses closed under right multiplication by a finite index subgroup H G. It is shown that for this extension of the satisfaction problem for G Z Z, 2-sat remains decidable while 3-sat becomes undecidable in ZFC. While supporting the paradigm, the proof does not argue on the basis of the inclusion 2-sat P and therefore does not immediately generalize. In view of the first two examples, w-limits seem to be a promising general approach to constructing decidable‡ limits of problems in P.

What follows are two speculations on how the introduction of ω-limits could have a role in distinguishing P from NP. The sketched arguments should be read as design criteria for limits that we do not know how to construct. The first is based on the preservation of connectivity under a continuous map. The second searches for a bridge to Gödel’s incompleteness theorem. Fix a non-principal ultrafilter ω Ž⁺ and let be the set of finite Boolean formulae on an infinite alphabet organized into a pointed metric space, or perhaps some weaker structure, in some manner which we do not yet know how to specify. Let be an ω-limit or some similar limit of . For the argument-plan we propose, the definition of the structure and the details of the limit taken must be such that is connected. However, it is necessary that if we restrict to ′ , a class of formulae which can be checked for satisfiability in poly-time, the limit yields a disconnected space ′. We suppose that the ω-satisfiability (1) or unsatisfiability (0) of = {f_i} can be defined by applying ω to the satisfiability of each f_i in a sequence defining . One can imagine that a polynomial time algorithm T could be rewritten “efficiently”—as in our choice of scanning function f into the positive orthant of Zⁿ—so that it would converge to a “continuous decision procedure” T: → {0, 1}, contradicting the connectivity of . The picture is that T would evolve through a succession (variable t) of complete state sequences (variable i) {S_i,t} defining a path with parameter t [0, 1] in S, the ω-limit of the discrete space of sequences of complete states {S_i}. Thus T would define a homotopy : × I → S whose end (F × 1) must be disconnected according to yes/no on ω-satisfiability. This would contradict the topological connectivity of .

The first-order theory A of arithmetic is known to contain weak fragments A⁻ for which there exists a decision procedure (carried out within first-order arithmetic, say by a Turing machine) for the provability in A of statements in A⁻. The best known example (and a high tide mark of Hilbert’s program to axiomatize mathematics) is Presberger Arithmetic PrA (8), which is essentially Peano arithmetic§ absent multiplication. Without multiplication, indexing of formulae cannot be achieved, so Presberger Arithmetic escapes Gödel’s incompleteness theorem. It seems plausible that a suitable ultrafilter limit could resurrect multiplication, since multiplication by any fixed integer is explicitly expressible as a repeated addition. Thus one might have a schematic formula on the level of ω-limits:

^c

I would like to express my thanks to Sam Buss and Hugh Woodin for stimulating conversations on the material presented. This work was partially supported by National Science Foundation Grant DMS 9501105, by Microsoft Research, and by the University of California, San Diego.