Proof theoretic complexity of low subrecursive classes

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Review text

In the paper under review a two-sorted version of Peano arithmetic is developed. Its proof-rules correspond to the normal/safe recursion schemes of Bellantoni and Cook. It is shown that now the provably recursive functions are brought down to more computationally realistic levels than in the single-sorted case, since the bounding functions turn out to be ``slow growing rather than ``fast growing. Results similar to earlier ones of Leivant are obtained -- they characterize classes \({\mathcal E}^{2}\) (in the existential fragment) and \({\mathcal E}^{3}\) (in the full theory) of the Grzegorczyk hierarchy.NEWLINENEWLINEFor the entire collection see [Zbl 0963.00029].

Recommendations

Cited in

(9)

This page was built for publication: Proof theoretic complexity of low subrecursive classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2752056)