A relationship between difference hierarchies and relativized polynomial hierarchies

DOI10.1007/BF01371729zbMath0776.68043MaRDI QIDQ5289273

Richard Beigel, Richard Chang, Mitsunori Ogiwara

Publication date: 22 August 1993

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

polynomial-time hierarchydifference hierarchy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ A downward translation in the polynomial hierarchy ⋮ Query order in the polynomial hierarchy ⋮ When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ On the power of deterministic reductions to C=P ⋮ Intersection suffices for Boolean hierarchy equivalence ⋮ Two queries ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ Proving SAT does not have small circuits with an application to the two queries problem ⋮ The 1-versus-2 queries problem revisited ⋮ On boolean lowness and boolean highness ⋮ Exact complexity of exact-four-colorability ⋮ Bounded queries to arbitrary sets ⋮ A Downward Collapse within the Polynomial Hierarchy ⋮ Query Order ⋮ Commutative queries ⋮ Bounded queries, approximations, and the Boolean hierarchy ⋮ A note on parallel queries and the symmetric-difference hierarchy. ⋮ Restrictive Acceptance Suffices for Equivalence Problems

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of combinatorial problems with succinct input representation
• Polynomial terse sets
• Bounded queries to SAT and the Boolean hierarchy
• A comparison of polynomial time reducibilities
• Some connections between bounded query classes and non-uniform complexity.
• PP is closed under intersection
• PP is closed under truth-table reductions
• Bounded Query Classes
• Sparse Sets, Lowness and Highness
• The difference and truth-table hierarchies for NP
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Boolean Hierarchy I: Structural Properties
• On the power of deterministic reductions to C=P
• Complexity classes defined by counting quantifiers
• On computing Boolean connectives of characteristic functions
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection