期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We investigate the phenomenon of depth-reduction in commutative
and non-commutative arithmetic circuits. We prove that in the
commutative setting, uniform semi-unbounded arithmetic circuits of
logarithmic depth are as powerful as uniform arithmetic circuits of
polynomial degree; earlier proofs did not work in the uniform
setting. This also provides a unified proof of the circuit
characterizations of LOGCFL and \#LOGCFL.
We show that AC1 has no more power than arithmetic circuits of
polynomial size and degree nO(loglogn) (improving the
trivial bound of nO(logn)). Connections are drawn between
TC1 and arithmetic circuits of polynomial size and degree.
Then we consider non-commutative computation, and show that some
depth reduction is possible over the algebra ( max,
concat), thus establishing that OptLOGCFL is in AC1. This is
the first depth-reduction result for arithmetic circuits over
a noncommutative semiring, and it complements the lower bounds of
\cite{nisan,kosaraju} showing that depth reduction cannot be done
in the general noncommutative setting.
We define new notions called ``short-left-paths'' and ``short-right-
paths'' and we show that these notions provide a characterization of
the classes of arithmetic circuits for which optimal depth-reduction
is possible. This class also can be characterized using the AuxPDA
model.
Finally, we characterize the languages generated by efficient
circuits over the (union, concat) semiring in terms of simple
one-way machines, and we investigate and extend earlier lower
bounds on non-commutative circuits.
