Stockmeyer induction (Q4035308)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 176204
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Stockmeyer induction |
scientific article; zbMATH DE number 176204 |
Statements
18 May 1993
0 references
polynomial time hierarchy
0 references
bounded arithmetic
0 references
provably total functions
0 references
0.730583906173706
0 references
0.7124266624450684
0 references
0.7023928165435791
0 references
Stockmeyer induction (English)
0 references
[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.
0 references
