Separating the low and high hierarchies by oracles
From MaRDI portal
Publication:2638773
DOI10.1016/0890-5401(91)90002-JzbMath0717.68033OpenAlexW2021084256MaRDI QIDQ2638773
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
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