A new recursion-theoretic characterization of the polytime functions (extended abstract)
Stephen J. Bellantoni, Stephen A Cook · 1992
We give a recursion-theoretic characterization of FP which describes polynomial time computation independently of any externally imposed resource bounds. In particular, this syntactic characterization avoids the explicit size bounds on recursion (and the initial function 2|x|.|y|) of Cobham.