Arithmetizing classes around {\textsf{NC}}^1 and {\textsf{L}}

DOI10.1007/S00224-009-9233-3MaRDI QIDQ968272zbMATH OpenOpenAlexFDO

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

Publication date 5 May 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-009-9233-3

zbMATH Keywords

branching programsarithmetizationbounded-width circuitscircuit degree

Mathematics Subject Classification ID

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

Recommendations

• Arithmetizing Classes Around NC 1 and 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\)
• Counting paths in VPA is complete for \#NC\(^{1}\)
• scientific article; zbMATH DE number 4041256

Cites work

• scientific article; zbMATH DE number 3876636 (Why is no real title available?)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 522856 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• An Optimal Parallel Algorithm for Formula Evaluation
• Arithmetizing Classes Around NC 1 and L
• Automata, Languages and Programming
• Boolean circuits versus arithmetic circuits
• Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Complexity theory of parallel time and hardware
• Division in logspace-uniform NC
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Nondeterministic NC^1 computation
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• On the Tape Complexity of Deterministic Context-Free Languages
• Properties that characterize LOGCFL
• The division breakthroughs
• Tree-size bounded alternation
• Two Applications of Inductive Counting for Complementation Problems
• Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
• Visibly pushdown languages
• \(\text{RL}\subseteq \text{SC}\)

Cited in

(7)

• Arithmetizing uniform NC
• Counting paths in VPA is complete for \#NC\(^{1}\)
• Counting paths in VPA is complete for \(\#\mathrm{NC}^1\)
• Arithmetizing Classes Around NC 1 and L
• 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}}
• Log-space algorithms for paths and matchings in k-trees

This page was built for publication: Arithmetizing classes around {\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 Q968272)