Arithmetizing Classes Around
\textsf{NC}
1 and
\textsf{L} |
| |
Authors: | Nutan Limaye Meena Mahajan B V Raghavendra Rao |
| |
Affiliation: | 1. The Institute of Mathematical Sciences, Chennai, 600113, India
|
| |
Abstract: | The parallel complexity class $\textsf{NC}$ 1 has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ 1 and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ 1. We also consider polynomial-degree restrictions of $\textsf{SC}$ i , denoted $\textsf{sSC}$ i , and show that the Boolean class $\textsf{sSC}$ 1 is sandwiched between $\textsf{NC}$ 1 and $\textsf{L}$ , whereas $\textsf{sSC}$ 0 equals $\textsf{NC}$ 1. On the other hand, the arithmetic class $\textsf{\#sSC}$ 0 contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ 1 contains $\textsf{\#NC}$ 1 and is in $\textsf{SC}$ 2. We also investigate some closure properties of the newly defined arithmetic classes. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|