A new Characterization of Type-2 Feasibility
Bruce M. Kapron, Stephen A Cook · SIAM Journal on Computing · 1996
K. Mehlhorn introduced a class of polynomial-time-computable operators in order to study poly-time reducibilities between functions. This class is defined using a generalization of A. Cobham's definition of feasibility for type-1 functions to type-2 functionals. Cobham's feasible functions are equivalent to the familiar poly-time functions. We generalize this equivalence to type-2 functionals. This requires a definition of the notion “poly time in the length of type-1 inputs.” The proof of this equivalence is not a simple generalization of the proof for type-1 functions; it depends on the fact that Mehlhorn’s class is closed under a strong form of simultaneous limited recursion on notation and requires an analysis of the structure of oracle queries in time-bounded computations.