Applicative theories for the polynomial hierarchy of time and its levels (Q1946672)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Applicative theories for the polynomial hierarchy of time and its levels |
scientific article; zbMATH DE number 6154066
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Applicative theories for the polynomial hierarchy of time and its levels |
scientific article; zbMATH DE number 6154066 |
Statements
Applicative theories for the polynomial hierarchy of time and its levels (English)
0 references
15 April 2013
0 references
In the paper under review applicative theories chracterizing the polynomial hierarchy of time (FPH) and its levels are introduced. They are based on a characterization of the functions in the polynomial hierarchy using monotonicity constraints introduced by Ben-Amram, Loff and Oitavem. Further, lower and upper bounds are considered. The proof of the lower bound follows from a straightforward embedding of the function algebra and the upper bound is carried out by an adaptation of the proofs given by Strahm.
0 references
computational complexity
0 references
levels of the polynomial hierarchy
0 references
applicative theories
0 references
induction schemes
0 references
polynomial hierarchy of time
0 references
