A downward translation in the polynomial hierarchy

DOI10.1007/BFB0023469zbMATH Open1498.68115OpenAlexW1498376507MaRDI QIDQ5048934FDOQ5048934

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

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

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)