A downward translation in the polynomial hierarchy

DOI10.1007/BFb0023469zbMath1498.68115OpenAlexW1498376507MaRDI QIDQ5048934

Hemaspaandra, Lane A., Harald Hempel, Edith Hemaspaandra

Publication date: 9 November 2022

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

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

Mathematics Subject Classification ID

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

Related Items (2)

Query order in the polynomial hierarchy ⋮ A Downward Collapse within the Polynomial Hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Downward translations of equality
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Upward separation for FewP and related classes
• Defying upward and downward separation
• STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
• Limitations of the upward separation technique
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• 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
• Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• Tally languages and complexity classes
• 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: A downward translation in the polynomial hierarchy