The Analytic Polynomial-Time Hierarchy

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

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,509

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.

Analytics

Added to PP
2014-01-16

Downloads
41 (#282,536)

6 months
1 (#417,896)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references