Arithmetizing classes around NC^1 and L.
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao · 2007
The parallel complexity class NC 1 has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. [CMTV98] considered arithmetizations of two of these classes, #NC¹ 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¹. We also consider polynomial-degree restrictions of SC i, denoted sSC i, and show that the Boolean class sSC¹ is sandwiched between NC¹ and L, whereas sSC⁰ equals NC¹. On the other hand, the arithmetic class #sSC⁰ contains #BWBP and is contained in FL, and #sSC¹ contains #NC^1 and is in SC². We also investigate some closure properties of the newly defined arithmetic classes. 1