Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-087 | 11th July 2007 00:00

Arithmetizing classes around NC^1 and L


Authors: Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao
Publication: 12th September 2007 20:47
Downloads: 1850


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.

ISSN 1433-8092 | Imprint