Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Arithmetizing Classes Around NC 1 and L
verfasst von : Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao
Erschienen in: STACS 2007
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The parallel complexity class
NC
1
has many equivalent models such as bounded width branching programs. Caussinus et.al [10] 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 has the same power as
#BWBP
, while counting proof-trees in logarithmic width formulae has the same power as
#NC
1
. We also consider polynomial-degree restrictions of
${\sf SC}^{i}$
, denoted
${\sf sSC}^{i}$
, and show that the Boolean class
${\sf sSC}{^1}$
lies between
NC
1
and
L
, whereas
${\sf sSC}^0$
equals
${\sf NC}^1$
. On the other hand,
${\sf \#}{\sf sSC}^0$
contains
#BWBP
and is contained in
FL
, and
#sSC
1
contains
#NC
1
and is in
${\sf SC}^{2}$
. We also investigate some closure properties of the newly defined arithmetic classes.