A second step toward the polynomial hierarchy
From MaRDI portal
Publication:1253656
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
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Hierarchies of computability and definability (03D55)
Related Items
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
