Predicative Recursion and The Polytime Hierarchy
Stephen J. Bellantoni · Birkhäuser Boston eBooks · 1995
Recent work in recursion theory has shown that the primitive recursive schemas can be modified so as to generate only the “feasible” class of polynomial time computable functions. In contrast to Cobham’s characterization, the new algebraic formulation uses a more structured form of recursion (“predicative recursion”) to avoid referring to polynomial growth bounds. The overall project is to rework recursion theory with respect to computational complexity, using predicativity as a guiding idea. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.