Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)

DOI10.1016/j.tcs.2011.05.050zbMath1282.68111OpenAlexW2221820168MaRDI QIDQ764326

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

zbMATH Keywords

complexity classesarithmetic circuits\(\mathrm{NC}^1\)exact counting classesoracle hierarchythreshold classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Parameterised counting in logspace ⋮ On measures of space over real and complex numbers

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