Counting classes and the fine structure between NC^1 and L

DOI10.1016/J.TCS.2011.05.050MaRDI QIDQ764326zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Counting classes and the fine structure between {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Nondeterministic NC^1 computation
• Parallel computation and the NC hierarchy relativized
• Arithmetizing Classes Around NC 1 and L
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}

Cites work

• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• Boolean circuits versus arithmetic circuits
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Counting classes and the fine structure between {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Nondeterministic NC^1 computation
• PP is closed under intersection
• PP is closed under truth-table reductions
• Relationships among $PL$, $\#L$, and the determinant
• Relativized circuit complexity
• Small-Space Analogues of Valiant’s Classes
• The PL Hierarchy Collapses
• The complexity of matrix rank and feasible systems of linear equations
• The difference and truth-table hierarchies for NP
• Unambiguity of circuits

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
• Arithmetizing Classes Around NC 1 and L
• Collapsing exact arithmetic hierarchies
• 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)