Commutative queries

DOI10.1006/INCO.2000.2918zbMath1007.03040OpenAlexW2913917660MaRDI QIDQ1854422

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

decision problemspolynomial hierarchyorder of oracle queriespolynomial-time Turing machines

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) 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 (3)

Query order in the polynomial hierarchy ⋮ Two queries ⋮ Query Order

Cites Work

• Unnamed Item
• Unnamed Item
• Some consequences of non-uniform conditions on uniform classes
• The complexity of facets (and some facets of complexity)
• Bounded queries to SAT and the Boolean hierarchy
• Quasi-linear truth-table reductions to \(p\)-selective sets
• Approximable sets
• Two queries
• On the commutativity of jumps
• Bounded Query Classes
• 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
• Query Order
• On computing Boolean connectives of characteristic functions
• Polynomial-Time Membership Comparable Sets
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• A relationship between difference hierarchies and relativized polynomial hierarchies

This page was built for publication: Commutative queries