Query Order

DOI10.1137/S0097539796297632MaRDI QIDQ4210168zbMATHOpenAlexFDO

Authors Lane A. Hemaspaandra, 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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• scientific article; zbMATH DE number 1091107
• Ordering conjunctive queries
• Extended order-generic queries
• Query order in the polynomial hierarchy
• scientific article; zbMATH DE number 1543293
• scientific article; zbMATH DE number 589881
• Ordering orders
• scientific article; zbMATH DE number 4002152
• The query complexity of order-finding

Cites work

• scientific article; zbMATH DE number 3592966 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1091107 (Why is no real title available?)
• A Downward Collapse within the Polynomial Hierarchy
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Bounded Query Classes
• Bounded queries to SAT and the Boolean hierarchy
• Commutative queries
• SELF-SPECIFYING MACHINES
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The difference and truth-table hierarchies for NP
• Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
• \(R_{1-tt}^{{\mathcal SN}}\)(NP) distinguishes robust many-one and Turing completeness

Cited in

(12)

• scientific article; zbMATH DE number 1091107 (Why is no real title available?)
• Query order in the polynomial hierarchy
• Query-monotonic Turing reductions
• scientific article; zbMATH DE number 1543293 (Why is no real title available?)
• SELF-SPECIFYING MACHINES
• Reducing the number of solutions of NP functions
• Ordering conjunctive queries
• Commutative queries
• Mind change speed-up for learning languages from positive data
• A note on parallel queries and the symmetric-difference hierarchy.
• Pinpointing computation with modular queries in the Boolean hierarchy
• Fine hierarchies and m-reducibilities in theoretical computer science

This page was built for publication: Query Order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210168)