Query Order

DOI10.1137/S0097539796297632zbMATH Open0915.68071OpenAlexW2914051656MaRDI QIDQ4210168FDOQ4210168

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Bounded queries to SAT and the Boolean hierarchy
• The Boolean Hierarchy II: Applications
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• A Downward Collapse within the Polynomial Hierarchy
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
• SELF-SPECIFYING MACHINES
• \(R_{1-tt}^{{\mathcal SN}}\)(NP) distinguishes robust many-one and Turing completeness
• Commutative queries

Cited In (10)

• Commutative queries
• SELF-SPECIFYING MACHINES
• Query order in the polynomial hierarchy
• Fine hierarchies and m-reducibilities in theoretical computer science
• Ordering conjunctive queries
• Query-monotonic Turing reductions
• Title not available (Why is that?)
• Reducing the number of solutions of NP functions
• A note on parallel queries and the symmetric-difference hierarchy.
• Mind change speed-up for learning languages from positive data

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• The query complexity of order-finding 👍 👎
• Extended order-generic queries 👍 👎
• Ordering conjunctive queries 👍 👎
• Ordering orders 👍 👎
• Query order in the polynomial hierarchy 👍 👎

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)