A Downward Collapse within the Polynomial Hierarchy

DOI10.1137/S0097539796306474MaRDI QIDQ4210153zbMATHOpenAlexFDO

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

zbMATH Keywords

polynomial hierarchycomputational complexity theorydownward collapseeasy-hard arguments

Mathematics Subject Classification ID

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)

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

Cites work

• A downward translation in the polynomial hierarchy
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Computation times of NP sets of different densities
• Defying upward and downward separation
• Downward translations of equality
• Easy sets and hard certificate schemes
• Limitations of the upward separation technique
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• Some observations on the probabilistic algorithms and NP-hard problems
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Tally languages and complexity classes
• 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

(14)

• Weak cardinality theorems
• Isolation and Reducibility Properties and the Collapse Result
• Commutative queries
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy
• Bounded queries, approximations, and the Boolean hierarchy
• The 1-versus-2 queries problem revisited
• The 1-Versus-2 Queries Problem Revisited
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
• A downward translation in the polynomial hierarchy
• The PL Hierarchy Collapses
• Query Order
• Two queries
• Fine hierarchies and m-reducibilities in theoretical computer science
• Tally NP sets and easy census functions.

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)