Defying upward and downward separation

DOI10.1006/inco.1995.1119zbMath0832.68046OpenAlexW1985125191MaRDI QIDQ1898109

Sudhir K. Jha, Hemaspaandra, Lane A.

Publication date: 20 February 1996

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

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)

Related Items (8)

One-way permutations and self-witnessing languages ⋮ A downward translation in the polynomial hierarchy ⋮ Strong self-reducibility precludes strong immunity ⋮ P-selectivity: Intersections and indices ⋮ A Downward Collapse within the Polynomial Hierarchy ⋮ SELF-SPECIFYING MACHINES ⋮ Resource bounded immunity and simplicity ⋮ Tally NP sets and easy census functions.

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