LIMITING POLYNOMIAL APPROXIMATION OF COMPLEXITY CLASSES
Giorgio Ausiello, Marco Protasi · International Journal of Foundations of Computer Science · 1990
The concept of limiting approximation, formerly introduced by Gold for recursive functions, is applied to the polynomial level of complexity in order to determine meaningful characterizations of classes of functions and sets which are not (or which are not known to be) polynomially computable. In particular, characterizations of NP, PSPACE and other classes of elementary functions are provided in terms of limiting polynomial approximation. In addition trade-offs between the space required by the approximating functions and the rate of convergence of the approximation are shown.