Defying upward and downward separation

DOI10.1006/INCO.1995.1119MaRDI QIDQ1898109zbMATH OpenOpenAlexFDO

Authors Sudhir K. Jha, Lane A. Hemaspaandra

Publication date 20 February 1996

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1006/inco.1995.1119

zbMATH Keywords

downward separation

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 512827
• Sparse sets and collapse of complexity classes
• Limitations of the upward separation technique
• Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
• scientific article; zbMATH DE number 4080914

Cited in

(14)

• Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
• Separating classes in the exponential-time hierarchy from classes in PH
• Tally NP sets and easy census functions.
• One-way permutations and self-witnessing languages
• Resource bounded immunity and simplicity
• Downward Separation Fails Catastrophically for Limited Nondeterminism Classes
• A Downward Collapse within the Polynomial Hierarchy
• scientific article; zbMATH DE number 1335875 (Why is no real title available?)
• scientific article; zbMATH DE number 512827 (Why is no real title available?)
• Strong self-reducibility precludes strong immunity
• A downward translation in the polynomial hierarchy
• SELF-SPECIFYING MACHINES
• P-selectivity: Intersections and indices
• The logics for the complexity classes with limited non-determinism

This page was built for publication: Defying upward and downward separation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1898109)