Query Order

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

zbMATH Keywords

computational complexity theorybounded queriesordered computation

Mathematics Subject Classification ID

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