Arithmetizing Classes Around $\textsf{NC}$ 1 and $\textsf{L}$

Abstract

The parallel complexity class 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, #NC 1 and #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 FLogDCFL , while counting proof-trees in logarithmic width formulae has the same power as #NC 1. We also consider polynomial-degree restrictions of SC i, denoted sSC i, and show that the Boolean class sSC 1 is sandwiched between NC 1 and L , whereas sSC 0 equals NC 1. On the other hand, the arithmetic class #sSC 0 contains #BWBP and is contained in FL , and #sSC 1 contains #NC 1 and is in SC 2. We also investigate some closure properties of the newly defined arithmetic classes.