Abstract:
The parallel complexity class NC^1 has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. \cite{CMTV} 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 Log, whereas sSC^0 equals NC^1. On the other hand, the arithmetic class #sSC^0 contains #BWBP and is contained in FLog, and #sSC^1 contains #NC^1 and is in SC^2. We also investigate some closure properties of the newly defined arithmetic classes.