Implicit characterizations of complexity classes
(Abstract)

Isabel Oitavem

Several machine independent approaches to relevant classes of computational complexity have been developed. All them lead to characterizations of classes of computational complexity where the machine formulation and resources are implicit -- implicit characterizations. Conceptually, implicit characterizations link computational complexity to levels of definitional and inferential abstractions of significant independent interest. In this course we focus on the class of functions computable in polynomial time, $\mbox{\sl {Ptime}}$. The first machine independent characterization of $\mbox{\sl {Ptime}}$   was given by Cobham in 1964. There are several nuances of the Cobham characterization, but all them use bounded recursion schemes which address to the resource constraints of $\mbox{\sl {Ptime}}$. Several years later, in 1992, Bellantoni and Cook came up with a remarkable characterization of $\mbox{\sl {Ptime}}$, where the use of input-sorted functions avoid the use of explicit bounds. In the same vein, but using two-sorted functions, Leivant also achieved a bound-free characterization of $\mbox{\sl {Ptime}}$. We describe and discuss these characterizations of $\mbox{\sl {Ptime}}$. In particular, we show that by removing the bounds on the Cobham's recursion scheme one gets functions of exponential growth. The aim of this course is to illustrate how sorted approaches can be used to build, in the classes, resource-independent mechanisms to control the growth of the functions. If the time allows we will extend this course to other classes of complexity.