Arithmetizing Classes Around NC 1 and L

DOI10.1007/978-3-540-70918-3_41zbMATH Open1186.68205OpenAlexW1589335334MaRDI QIDQ3590957FDOQ3590957

Authors: Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao 

Publication date: 3 September 2007

Published in: STACS 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70918-3_41

Recommendations

• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Counting classes and the fine structure between {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
• scientific article; zbMATH DE number 4041256
• Some classes of languages in \(NC^ 1\)

Mathematics Subject Classification ID

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

Cited In (10)

• Arithmetizing uniform \(NC\)
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• Resource trade-offs in syntactically multilinear arithmetic circuits
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Counting paths in VPA is complete for \#NC\(^{1}\)
• Counting paths in VPA is complete for \(\#\mathrm{NC}^1\)
• Small space analogues of Valiant's classes and the limitations of skew formulas
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
• Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
• Counting classes and the fine structure between {\textsf{NC}}\(^{1}\) and {\textsf{L}}

This page was built for publication: Arithmetizing Classes Around NC 1 and L

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