The Analytic Polynomial-Time Hierarchy

Mathematical Logic Quarterly 44 (4):529-544 (1998)

Motivated by results on interactive proof systems we investigate an ∃-∀hierarchy over P using word quantifiers as well as two types of set quantifiers. This hierarchy, which extends the polynomial-time hierarchy, is called the analytic polynomial-time hierarchy. It is shown that every class of this hierarchy coincides with one of the following Classes: ∑math image, Πmath image , PSPACE, ∑math image or Πmath image . This improves previous results by Orponen [6] and allows interesting comparisons with the above mentioned results on inter-active proof systems
Keywords Oracles  Complexity theory  Polynomial‐time hierarchies  Quantifiers  Set operators
Categories (categorize this paper)
DOI 10.1002/malq.19980440412
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,683
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
Polynomial Time Operations in Explicit Mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Light Affine Lambda Calculus and Polynomial Time Strong Normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Admissible Closures of Polynomial Time Computable Arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5-6):643-660.
Consequences of the Provability of NP ⊆ P/Poly.Stephen Cook & Jan Krajíček - 2007 - Journal of Symbolic Logic 72 (4):1353 - 1371.


Added to PP index

Total views
32 ( #253,132 of 2,242,901 )

Recent downloads (6 months)
3 ( #625,882 of 2,242,901 )

How can I increase my downloads?


My notes

Sign in to use this feature