Commutative queries

DOI10.1006/INCO.2000.2918MaRDI QIDQ1854422zbMATH OpenOpenAlexFDO

Authors Richard Beigel, Richard Chang

Publication date 14 January 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.2000.2918

zbMATH Keywords

polynomial hierarchydecision problemsorder of oracle queriespolynomial-time Turing machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• Query order in the polynomial hierarchy
• scientific article; zbMATH DE number 1091107
• scientific article; zbMATH DE number 512846
• scientific article; zbMATH DE number 1543293
• Query Order

Cites work

• scientific article; zbMATH DE number 512828 (Why is no real title available?)
• scientific article; zbMATH DE number 1543293 (Why is no real title available?)
• A Downward Collapse within the Polynomial Hierarchy
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Approximable sets
• Bounded Query Classes
• Bounded queries to SAT and the Boolean hierarchy
• On computing Boolean connectives of characteristic functions
• On the commutativity of jumps
• Polynomial-Time Membership Comparable Sets
• Quasi-linear truth-table reductions to \(p\)-selective sets
• Query Order
• Some consequences of non-uniform conditions on uniform classes
• 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 complexity of facets (and some facets of complexity)
• Two queries

Cited in

(5)

• Query order in the polynomial hierarchy
• scientific article; zbMATH DE number 1543293 (Why is no real title available?)
• Two queries
• Query Order
• Oracles That Compute Values

This page was built for publication: Commutative queries

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