A Downward Collapse within the Polynomial Hierarchy
From MaRDI portal
Publication:4210153
DOI10.1137/S0097539796306474zbMath0915.68070OpenAlexW2020903247MaRDI QIDQ4210153
Edith Hemaspaandra, Harald Hempel, Hemaspaandra, Lane A.
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
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)
Related Items
Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies, Two queries, The 1-Versus-2 Queries Problem Revisited, Fine hierarchies and m-reducibilities in theoretical computer science, Weak cardinality theorems, The 1-versus-2 queries problem revisited, Query Order, Tally NP sets and easy census functions., Commutative queries, Bounded queries, approximations, and the Boolean hierarchy
Cites Work
- Downward translations of equality
- Some observations on the probabilistic algorithms and NP-hard problems
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Upward separation for FewP and related classes
- Computation times of NP sets of different densities
- Easy sets and hard certificate schemes
- Defying upward and downward separation
- 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 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 downward translation in the polynomial hierarchy
- A relationship between difference hierarchies and relativized polynomial hierarchies
