Predicative analysis of recursion schema is a method to characterizecomplexity classes like the class FPTIME of polynomial time computablefunctions. This analysis comes from the works of Bellantoni and Cook, andLeivant by data tiering. Here, we refine predicative analysis by using aramified Ackermann's construction of a non-primitive recursive function. Weobtain a hierarchy of functions which characterizes exactly functions, whichare computed in O(nk) time over register machine model ofcomputation. For this, we introduce a strict ramification principle. Then, weshow how to diagonalize in order to obtain an exponential function and to jumpoutside deterministic polynomial time. Lastly, we suggest a dependent typedlambda-calculus to represent this construction.
展开▼
