Counting classes and the fine structure between {\textsf{NC}}^1 and {\textsf{L}}

DOI10.1007/978-3-642-15155-2_28MaRDI QIDQ3586093zbMATH OpenOpenAlexFDO

Authors

Publication date 3 September 2010

Published in Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15155-2_28

Mathematics Subject Classification ID

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

Recommendations

• Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
• Arithmetizing Classes Around NC 1 and L
• Nondeterministic NC^1 computation
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Mathematical Foundations of Computer Science 2003

Cited in

(7)

• Nondeterministic NC^1 computation
• Succinct algebraic branching programs characterizing non-uniform complexity classes
• Comparing counting classes for logspace, one-way logspace, and first-order
• Arithmetizing Classes Around NC 1 and L
• Collapsing exact arithmetic hierarchies
• Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}

This page was built for publication: Counting classes and the fine structure between {\textsf{NC}}\(^{1}\) and {\textsf{L}}

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586093)