Query Order
From MaRDI portal
Publication:4210168
DOI10.1137/S0097539796297632zbMath0915.68071OpenAlexW2914051656MaRDI QIDQ4210168
Hemaspaandra, Lane A., Harald Hempel, Gerd Wechsung
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539796297632
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)
Related Items
Query order in the polynomial hierarchy, Query-monotonic Turing reductions, Mind change speed-up for learning languages from positive data, Fine hierarchies and m-reducibilities in theoretical computer science, SELF-SPECIFYING MACHINES, Commutative queries, A note on parallel queries and the symmetric-difference hierarchy., Reducing the number of solutions of NP functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounded queries to SAT and the Boolean hierarchy
- \(R_{1-tt}^{{\mathcal SN}}\)(NP) distinguishes robust many-one and Turing completeness
- Commutative queries
- 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
- The Boolean Hierarchy II: Applications
- A Downward Collapse within the Polynomial Hierarchy
- Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- SELF-SPECIFYING MACHINES
- A relationship between difference hierarchies and relativized polynomial hierarchies
