Stockmeyer induction

MaRDI QIDQ4035308zbMATH OpenFDO

Authors Fernando Ferreira

Publication date 18 May 1993

zbMATH Keywords

bounded arithmeticpolynomial time hierarchyprovably total functions

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Review text

[For the entire collection see Zbl 0753.00018.] This paper presents a hierarchy of first-order theories whose standard models have as their domain the set of binary words \(\{0,1\}^*\). These theories have as their basic feature the fact that induction is restricted to formulae that define a particular level of the Meyer- Stockmeyer (or polynomial time) hierarchy. This hierarchy of theories is a reformulation of Samuel Buss' well known first-order systems of bounded arithmetic. The main results (up to 1990) concerning the relationships between the theories, and the provably total functions of these theories, are proved by novel techniques.

Recommendations

• Delineating classes of computational complexity via second order theories with weak set existence principles. I
• scientific article; zbMATH DE number 4059391
• scientific article; zbMATH DE number 999649
• Restricted polynomial induction versus ordinary induction
• Bounded arithmetic and truth definition

Cited in

(7)

• Binary models generated by their tally part
• Theories with self-application and computational complexity.
• Separating NC along the \(\delta\) axis
• Introduction to clarithmetic. II
• Admissible closures of polynomial time computable arithmetic
• Enumerating error bounded polytime algorithms through arithmetical theories
• Schubert induction

This page was built for publication: Stockmeyer induction

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