zbMATH — the first resource for mathematics

Applicative theories for the polynomial hierarchy of time and its levels. (English) Zbl 1275.03131
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.

03D15 Complexity of computation (including implicit computational complexity)
03D55 Hierarchies of computability and definability
03F30 First-order arithmetic and fragments
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI