A note on sparse sets and the polynomial-time hierarchy
From MaRDI portal
Publication:1263964
DOI10.1016/0020-0190(89)90193-2zbMath0688.68029MaRDI QIDQ1263964
Publication date: 1989
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(89)90193-2
68Q25: Analysis of algorithms and problem complexity
Related Items
Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, A refinement of the low and high hierarchies
Cites Work
- Unnamed Item
- A low and a high hierarchy within NP
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- On Restricting the Size of Oracles Compared with Restricting Access to Oracles
- Quantitative Relativizations of Complexity Classes
- Sparse Sets, Lowness and Highness