Marion, Jean-Yves - On tiered small jump operators

lmcs:1146 - Logical Methods in Computer Science, March 31, 2009, Volume 5, Issue 1
On tiered small jump operators

Authors: Marion, Jean-Yves

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.


Source : oai:arXiv.org:0903.2410
DOI : 10.2168/LMCS-5(1:7)2009
Volume: Volume 5, Issue 1
Published on: March 31, 2009
Submitted on: March 13, 2008
Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,F.2.0


Share

Consultation statistics

This page has been seen 35 times.
This article's PDF has been downloaded 19 times.