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

The parallel complexity class $textsf{NC}$ ¹ 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}$ ¹ 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}$ ¹. We also consider polynomial-degree restrictions of $textsf{SC}$ ⁱ , denoted $textsf{sSC}$ ⁱ , and show that the Boolean class $textsf{sSC}$ ¹ is sandwiched between $textsf{NC}$ ¹ and $textsf{L}$ , whereas $textsf{sSC}$ ⁰ equals $textsf{NC}$ ¹. On the other hand, the arithmetic class $textsf{#sSC}$ ⁰ contains $textsf{#BWBP}$ and is contained in $textsf{FL}$ , and $textsf{#sSC}$ ¹ contains $textsf{#NC}$ ¹ and is in $textsf{SC}$ ². We also investigate some closure properties of the newly defined arithmetic classes.