Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
From MaRDI portal
Publication:4717047
DOI10.1051/ita/1996300201011zbMath0860.68048MaRDI QIDQ4717047
Publication date: 13 April 1997
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92527
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Adaptive logspace reducibility and parallel time, The structure of logarithmic advice complexity classes, Locating \(P\)/poly optimally in the extended low hierarchy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
- A low and a high hierarchy within NP
- Complexity and structure
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On truth-table reducibility to SAT
- Bounded queries to SAT and the Boolean hierarchy
- Logarithmic advice classes
- A note on sparse sets and the polynomial-time hierarchy
- Sets with small generalized Kolmogorov complexity
- On the Decomposability of $NC$ and $AC$
- Self-reducible sets of small density
- Bounded Query Classes
- On Circuit-Size Complexity and the Low Hierarchy in NP
- RelativizedNC
- The difference and truth-table hierarchies for NP
- The Boolean Hierarchy I: Structural Properties
- Lower bounds for the low hierarchy
- Complete sets and closeness to complexity classes
