Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
From MaRDI portal
Publication:764326
DOI10.1016/j.tcs.2011.05.050zbMath1282.68111OpenAlexW2221820168MaRDI QIDQ764326
Publication date: 13 March 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.050
complexity classesarithmetic circuits\(\mathrm{NC}^1\)exact counting classesoracle hierarchythreshold classes
Related Items
Cites Work
- Unnamed Item
- Relativized circuit complexity
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Unambiguity of circuits
- Nondeterministic \(NC^1\) computation
- PP is closed under intersection
- PP is closed under truth-table reductions
- The complexity of matrix rank and feasible systems of linear equations
- Boolean circuits versus arithmetic circuits
- Small-Space Analogues of Valiant’s Classes
- Counting Classes and the Fine Structure between NC 1 and L
- The difference and truth-table hierarchies for NP
- The PL Hierarchy Collapses
- Relationships among $PL$, $\#L$, and the determinant