Mehlhorn obtained his definition of type-2 polynomial-time by relativizing Cobham's [1] original definition of polynomial-time. Mehlhorn's class is characterized as the smallest class containing certain type-1 polynomial-time functions and the type-2 application functional, which is closed under composition and bounded recursion on notation. The latter is a variant of primitive recursion in which the recursion is based on the binary notation of a numerical input, and for which the final result can be bounded by a function in the class.
Type-2 computability comes in three basic flavors. The following is a brief description of each.
In order to define resource-bounded versions of these models, we must answer a basic question: how do we measure resource usage as a uniform function of input size? More specifically, what is the ``size'' of a function input? In [3] the following answer is provided: if f is a function from N to N, then |f|, the size of f, is the function \n.max{|f(x)| : |x| <= n}. The idea behind this is that if the cost associated with querying an input oracle f at some y is |f(y)|, then |f| gives a uniform measure of the cost of accessing f over all inputs up to a given size. Given this definition of the size of a function input, there is a natural definition of being polynomial in the size of a function input.
Kapron and Cook show that the class total recursive functionals which are computed by oracle Turing machines with running time polynomial in the size of their function inputs correspond exactly to Mehlhorn's class. This result is not merely a relativization of Cobham's original characterization result. A major difficulty lies in the the fact that the functional \f \n. |f|(n) is not in Mehlhorn's class. The essential observation made in [3] is that the full power of |f| is not required, since the running time can only depend on those values of f which are actually queried during the computation. This is also the basis for Seth's notion of clocking for type-2 polynomial-time functionals. In Seth's model, machines have clocks which are updated using the size of oracle answers, The clocking notion also is essential in Royer's definition of a polynomial-time version of the effective operations. In Royer's model, such operations are computed by clocked Turing machines which may perform any operation on the code corresponding to its function input. However, the clock is updated only in the case where the code is accessed by a special subroutine which simulates the computation of the corresponding recursive function on a given numerical input. In this case, the number of steps in the simulation is used to do the update, rather than the size of the result.
An important result of type-2 recursion theory, the Kreisel-Lacombe-Shoenfield theorem, states that when restricted to total recursive inputs, the total effective operations correspond to the effective continuous functionals. This correspondence can also be extended to include the partial recursive functionals. Royer considered a polynomial-time version of this result, and was able to show that if, when restricted to total recursive inputs, the clocked polynomial-time effective operations correspond to Mehlhorn's class, then P is not equal to NP. Hence proving such a result will be extremely difficult. However, if the notion of effective operation is weakened to allow functionals only to access computations of their function inputs, rather than their program code, then a correspondence can be established.
Recently, Kapron proposed a definition for poly-time effective continuous functionals, and conjectured that when restricted to total inputs, these coincide with Mehlhorn's class. Royer has shown that if this conjecture holds, then there is a poly-time factorization algorithm.