arXiv Analytics

Sign in

arXiv:1306.5559 [math.LO]AbstractReferencesReviewsResources

Characterising Complexity Classes by Inductive Definitions in Bounded Arithmetic

Naohi Eguchi

Published 2013-06-24, updated 2014-01-20Version 4

Famous descriptive characterisations of P and PSPACE are restated in terms of the Cook-Nguyen style second order bounded arithmetic. We introduce an axiom of inductive definitions over second order bounded arithmetic. We show that P can be captured by the axiom of inflationary inductive definitions whereas PSPACE can be captured by the axiom of non-inflationary inductive definitions.

Comments: Technical report
Categories: math.LO
Related articles:
arXiv:1205.2879 [math.LO] (Published 2012-05-13)
A Simplified Characterisation of Provably Computable Functions of the System ID_1 of Inductive Definitions
arXiv:1508.06556 [math.LO] (Published 2015-08-26)
The Power of the Depth of Iteration in Defining Relations by Induction

Links

Toolbox