Separating the low and high hierarchies by oracles

DOI10.1016/0890-5401(91)90002-JzbMath0717.68033OpenAlexW2021084256MaRDI QIDQ2638773

Ker-I. Ko

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1016/0890-5401(91)90002-j

zbMATH Keywords

oracleshigh hierarchylow hierarchy

Mathematics Subject Classification ID

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

Related Items (6)

The join can lower complexity ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ UP and the low and high hierarchies: A relativized separation ⋮ Black-Box and Data-Driven Computation ⋮ UP and the low and high hierarchies: A relativized separation ⋮ Boolean operations, joins, and the extended low hierarchy

Cites Work

• Unnamed Item
• A low and a high hierarchy within NP
• Strong nondeterministic polynomial-time reducibilities
• The polynomial-time hierarchy and sparse oracles
• Parity, circuits, and the polynomial-time hierarchy
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Relativized Polynomial Time Hierarchies Having Exactly K Levels

This page was built for publication: Separating the low and high hierarchies by oracles