Complete and tractable machine-independent characterizations of second-order polytime

Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion +1

The class of Basic Feasible Functionals BFF is the second-order counterpart of the class of first-order functions computable in polynomial time. We present several implicit charact…