Ramified Recurrence and Computational Complexity I: Word Recurrence and Poly-time
Daniel M. Leivant · Birkhäuser Boston eBooks · 1995
We exhibit a notion of recurrence over free algebras ramified into tiers, based on unfolding an implicit circularity of the recurrence schema; recurrence in two tiers was introduced independently in [4, 13, 24].) We show that the functions generated by ramified recurrence over a word algebra $$\mathbb{A}$$ are obtained already using only two tiers, and are exactly the functions computable by a register machine over $$\mathbb{A}$$ in time polynomial in the length of the input. For the algebra $$\mathbb{W}$$ of words over a binary alphabet, these are exactly the poly-time functions in the usual sense, as shown in [4]. When the medium of computation is the algebra ℕ of unary numerals, then the numeric functions generated are exactly the ones computable in linear space, as shown independently in [2, 10, 21]. These characterizations are purely functional, use neither initial functions other than the algebra constructors nor restrictions on rate of growth or computational resources, and use recurrence over the algebra in hand (rather than “recursion on notations” as in [6]). Moreover, computability in time O(n k ) corresponds exactly to k nestings of ramified simultaneous recurrence, if only two tiers are used. If higher tiers are used then k corresponds to a certain recurrence-degree that combines counts of recurrence and composition. Finally, we define nondeterministic recurrence, and observe that ramified nondeterministic recurrence over word algebras yields exactly NP for non-unary algebras, but is conservative over ramified recurrence for unary algebras.