Computer Science – Computational Complexity
Scientific paper
2009-03-13
LMCS 5 (1:7) 2009
Computer Science
Computational Complexity
Scientific paper
10.2168/LMCS-5(1:7)2009
Predicative analysis of recursion schema is a method to characterize complexity classes like the class FPTIME of polynomial time computable functions. This analysis comes from the works of Bellantoni and Cook, and Leivant by data tiering. Here, we refine predicative analysis by using a ramified Ackermann's construction of a non-primitive recursive function. We obtain a hierarchy of functions which characterizes exactly functions, which are computed in O(n^k) time over register machine model of computation. For this, we introduce a strict ramification principle. Then, we show how to diagonalize in order to obtain an exponential function and to jump outside deterministic polynomial time. Lastly, we suggest a dependent typed lambda-calculus to represent this construction.
No associations
LandOfFree
On tiered small jump operators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On tiered small jump operators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On tiered small jump operators will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-229021