Title: Predicative Recursion and The Polytime Hierarchy
Abstract: 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.
Publication Year: 1995
Publication Date: 1995-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 46
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot