Applicative theories for the polynomial hierarchy of time and its levels. (English) Zbl 1275.03131

Kahle, Reinhard; Oitavem, Isabel

Ann. Pure Appl. Logic 164, No. 6, 663-675 (2013).

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.

Reviewer: Roman Murawski (Poznań)

MSC:

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.)

Keywords:

computational complexity; levels of the polynomial hierarchy; applicative theories; induction schemes; polynomial hierarchy of time