A Downward Collapse within the Polynomial Hierarchy
DOI10.1137/S0097539796306474zbMATH Open0915.68070OpenAlexW2020903247MaRDI QIDQ4210153FDOQ4210153
Authors: Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel 
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539796306474
Recommendations
- A downward translation in the polynomial hierarchy
- On collapsing the polynomial-time hierarchy
- Descent polynomials
- A generalization of descent polynomials
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Publication:4944898
- The descent set polynomial revisited
- scientific article; zbMATH DE number 3880901
- Publication:4936674
- Hyper-polynomial hierarchies and the polynomial jump
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
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 II: Applications
- Tally languages and complexity classes
- Computation times of NP sets of different densities
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Upward separation for FewP and related classes
- Some observations on the probabilistic algorithms and NP-hard problems
- Defying upward and downward separation
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- Easy sets and hard certificate schemes
- Downward translations of equality
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
- Limitations of the upward separation technique
- A downward translation in the polynomial hierarchy
Cited In (13)
- Commutative queries
- The 1-versus-2 queries problem revisited
- Tally NP sets and easy census functions.
- Weak cardinality theorems
- Isolation and Reducibility Properties and the Collapse Result
- The PL Hierarchy Collapses
- Fine hierarchies and m-reducibilities in theoretical computer science
- Two queries
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
- Query Order
- Bounded queries, approximations, and the Boolean hierarchy
- The 1-Versus-2 Queries Problem Revisited
This page was built for publication: A Downward Collapse within the Polynomial Hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210153)
