2013/06/24 by Naohi Eguchi, Eguchi, Naohi
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #math.LO
paper · pdf · doi:10.48550/arxiv.1306.5559
Technical report
openalex publication_date 2013/06/24 · arxiv created 2014/01/20 · arxiv updated 2014/01/21 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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.