In the first part of the talk we present the Bellantoni-Cook characterization of FPtime. This is a purely recursion-theoretic description of the polytime functions, which avoids the explicit bounded recursion scheme used in Cobham's approach to FPtime. In the second part, we will show how to reach the class NP within the same framework.
Kolloquium
