Applicative theories for the polynomial hierarchy of time and its levels
type: Item
instance of: scholarly article
title: Applicative theories for the polynomial hierarchy of time and its levels
zbMATH Open document ID: 1275.03131
author: Reinhard Kahle
author: Isabel Oitavem
published in: Annals of Pure and Applied Logic
publication date: 2013-04-15T00:00:00Z
review text: 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.
reviewed by: Roman Murawski
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D55
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6154066
zbMATH Keywords: computational complexity
zbMATH Keywords: levels of the polynomial hierarchy
zbMATH Keywords: applicative theories
zbMATH Keywords: induction schemes
zbMATH Keywords: polynomial hierarchy of time
MaRDI profile type: Publication
full work available at URL: j.apal.2012.05.006
OpenAlex ID: W2042217238
DOI: 10.1016/J.APAL.2012.05.006
description: scientific article; zbMATH DE number 6154066