A second step toward the polynomial hierarchy

DOI10.1016/0304-3975(79)90043-4zbMath0397.03023OpenAlexW2089914953MaRDI QIDQ1253656

Theodore P. Baker, Selman, Alan L.

Publication date: 1979

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(79)90043-4

zbMATH Keywords

Computational ComplexityPolynomial HierarchyRecursive Oracle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Hierarchies of computability and definability (03D55)

Related Items (28)

Continuous optimization problems and a polynomial hierarchy of real functions ⋮ On \(\Delta ^ P_ 2\)-immunity ⋮ Positive relativizations for log space computability ⋮ Relativized alternation and space-bounded computation ⋮ Probabilistic quantifiers and games ⋮ Simplicity, immunity, relativizations and nondeterminism ⋮ Relativized Arthur-Merlin versus Merlin-Arthur games ⋮ With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy ⋮ A refinement of the low and high hierarchies ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ Optimization problems and the polynomial hierarchy ⋮ Bounded query machines: on NP and PSPACE ⋮ Bounded query machines: on NP( ) and NPQUERY( ) ⋮ On counting problems and the polynomial-time hierarchy ⋮ Restricted relativizations of probabilistic polynomial time ⋮ A second step toward the strong polynomial-time hierarchy ⋮ Parity, circuits, and the polynomial-time hierarchy ⋮ Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets ⋮ A uniform approach to define complexity classes ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Log space machines with multiple oracle tapes ⋮ Unnamed Item ⋮ On languages specified by relative acceptance ⋮ Relativizing relativized computations ⋮ Generix strikes again ⋮ A low and a high hierarchy within NP ⋮ On some natural complete operators ⋮ On the complexity of counting in the polynomial hierarchy

Cites Work

• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Recursive Predicates and Quantifiers

This page was built for publication: A second step toward the polynomial hierarchy