Intersection suffices for Boolean hierarchy equivalence

DOI10.1007/bfb0030862zbMath1527.68078OpenAlexW1580209692MaRDI QIDQ6085737

Hemaspaandra, Lane A., 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)

Cites Work

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

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