Query order in the polynomial hierarchy
From MaRDI portal
Publication:5055937
DOI10.1007/BFb0036186OpenAlexW1488148209MaRDI QIDQ5055937
Harald Hempel, Edith Hemaspaandra, Hemaspaandra, Lane A.
Publication date: 9 December 2022
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bfb0036186
Related Items (2)
Query order in the polynomial hierarchy ⋮ A note on parallel queries and the symmetric-difference hierarchy.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(R_{1-tt}^{{\mathcal SN}}\)(NP) distinguishes robust many-one and Turing completeness
- Commutative queries
- PP is closed under truth-table reductions
- Bounded Query Classes
- The difference and truth-table hierarchies for NP
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- The Boolean Hierarchy I: Structural Properties
- Query Order
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- A downward translation in the polynomial hierarchy
- Query order in the polynomial hierarchy
- A relationship between difference hierarchies and relativized polynomial hierarchies
This page was built for publication: Query order in the polynomial hierarchy
