A Downward Collapse within the Polynomial Hierarchy

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

zbMATH Keywords

polynomial hierarchycomputational complexity theorydownward collapseeasy-hard arguments

Mathematics Subject Classification ID

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