A predicative approach to the classification problem

Abstract

We harmonize many time-complexity classes DTIMEF ( f ( n )) ( f ( n ) [ges ] n ) with the PR functions (at and above the elementary level) in a transfinite hierarchy of classes of functions [Tscr ] α . Class [Tscr ] α is obtained by means of unlimited operators, namely: a variant Π of the predicative or safe recursion scheme, introduced by Leivant, and by Bellantoni and Cook, if α is a successor; and constructive diagonalization if α is a limit. Substitution ( SBST ) is discarded because the time complexity classes are not closed under this scheme. [Tscr ] α is a structure for the PR functions finer than [Escr ] α , to the point that we have [Tscr ] ε 0 = [Escr ] 3 (elementary functions). Although no explicit use is made of hierarchy functions, it is proved that f ( n ) ∈ [Tscr ] α implies f ( n ) [les ] n G α ( n ) , where G α belongs to the slow growing hierarchy (of functions) studied, in particular, by Girard and Wainer.