Counting classes and the fine structure between NC^1 and L
From MaRDI portal
Publication:764326
DOI10.1016/J.TCS.2011.05.050zbMATH Open1282.68111OpenAlexW2221820168MaRDI QIDQ764326FDOQ764326
Authors: D. Kharzeev 
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
Recommendations
complexity classesarithmetic circuits\(\mathrm{NC}^1\)exact counting classesoracle hierarchythreshold classes
Cites Work
- Nondeterministic \(NC^1\) computation
- Title not available (Why is that?)
- Boolean circuits versus arithmetic circuits
- Relativized circuit complexity
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- The difference and truth-table hierarchies for NP
- PP is closed under intersection
- Relationships among $PL$, $\#L$, and the determinant
- The complexity of matrix rank and feasible systems of linear equations
- PP is closed under truth-table reductions
- Unambiguity of circuits
- Small-Space Analogues of Valiant’s Classes
- Counting classes and the fine structure between {\textsf{NC}}\(^{1}\) and {\textsf{L}}
- The PL Hierarchy Collapses
Cited In (7)
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
- Mathematical Foundations of Computer Science 2003
- Parameterised counting in logspace
- On measures of space over real and complex numbers
- Collapsing exact arithmetic hierarchies
- Arithmetizing Classes Around NC 1 and L
- Counting classes and the fine structure between {\textsf{NC}}\(^{1}\) and {\textsf{L}}
This page was built for publication: Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764326)
