Intersection suffices for Boolean hierarchy equivalence

DOI10.1007/BFB0030862MaRDI QIDQ6085737zbMATH OpenOpenAlexFDO

Authors Lane A. Hemaspaandra, Jörg Rothe

Publication date 12 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0030862

Mathematics Subject Classification ID

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

Recommendations

• The Boolean Hierarchy I: Structural Properties
• Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
• scientific article; zbMATH DE number 1222828
• scientific article; zbMATH DE number 3988706
• scientific article; zbMATH DE number 3930351

Cites work

• A relationship between difference hierarchies and relativized polynomial hierarchies
• BANISHING ROBUST TURING COMPLETENESS
• Complexity classes without machines: on complete languages for UP
• Downward Separation Fails Catastrophically for Limited Nondeterminism Classes
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
• scientific article; zbMATH DE number 17529 (Why is no real title available?)
• scientific article; zbMATH DE number 512827 (Why is no real title available?)
• On computing Boolean connectives of characteristic functions
• On the unique satisfiability problem
• Relative complexity of checking and evaluating
• Separating complexity classes with tally oracles
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• The complexity of facets (and some facets of complexity)
• The complexity of theorem-proving procedures
• The difference and truth-table hierarchies for NP
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The polynomial-time hierarchy

This page was built for publication: Intersection suffices for Boolean hierarchy equivalence

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