A downward translation in the polynomial hierarchy

DOI10.1007/BFB0023469MaRDI QIDQ5048934zbMATH OpenOpenAlexFDO

Authors Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel

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)

Recommendations

• A Downward Collapse within the Polynomial Hierarchy
• scientific article; zbMATH DE number 1304327
• On the Structure of Bounded Queries to Arbitrary NP Sets
• Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries
• Defying upward and downward separation

Cites work

• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 17529 (Why is no real title available?)
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Defying upward and downward separation
• Downward translations of equality
• Limitations of the upward separation technique
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Tally languages and complexity classes
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The difference and truth-table hierarchies for NP
• Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
• Upward separation for FewP and related classes
• BPP has subexponential time simulations unless EXPTIME has publishable proofs

Cited in

(3)

• Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries
• Query order in the polynomial hierarchy
• A Downward Collapse within the Polynomial Hierarchy

This page was built for publication: A downward translation in the polynomial hierarchy

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