Applicative theories for the polynomial hierarchy of time and its levels (Q1946672)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Applicative theories for the polynomial hierarchy of time and its levels |
scientific article |
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