Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds
复制标题
非交换算术电路：深度缩减和尺寸下界
DOI：
10.1016/s0304-3975(97)00227-2
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
V. Vinay
中科院分区：
文献类型：
--
作者：
Eric Allender;Jia Jiao;M. Mahajan;V. Vinay
我们研究了交换和非交换算术电路中的深度缩减现象。证明了在交换环境下，对数深度的一致半无界算术电路与多项式次数(且深度不受限)的一致算术电路一样强大；以前的证明在一致环境下不起作用。这也提供了类LOGCFL及其计数变量#LOGCFL的电路特征的统一证明。我们证明了AC1的能力并不比多项式大小和次数为no(Loglogn)的算术电路多(改进了no(Logn)的平凡界)。在TC1和多项式大小和次数的算术电路之间画出连接。然后我们考虑非对易计算。我们证明了在代数(∑∗，MAX，CONCAT)上，多项式大小和多项式次数的算术电路可以减少到O(Log2n)深度(如果允许无界扇入门，甚至可以减少到O(Logn)深度)。这将确定OptLOGCFL位于AC1中。这是非对易半环上算术电路深度约简的第一个结果，它补充了Kosaraju和Nisan关于一般非对易环境下不能进行深度约简的下界。我们定义了称为“左短路”和“右短路”的新概念，并且证明了这些概念提供了最优深度缩减可能的算术电路类的特征。这个类也可以使用AuxPDA模型来描述。最后，我们用简单的单向机刻画了半环(2∑∗，并，并)上的有效圈生成的语言，并研究和推广了早期的非对易圈的下界。
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 (and unrestricted depth); earlier proofs did not work in the uniform setting. This also provides a unified proof of the circuit characterizations of the class LOGCFL and its counting variant #LOGCFL. We show that AC1has no more power than arithmetic circuits of polynomial size and degree nO(loglogn)(improving the trivial bound of nO(logn)). Connections are drawn between TC1and arithmetic circuits of polynomial size and degree. Then we consider non-commutative computation. We show that over the algebra (∑∗, max, concat), arithmetic circuits of polynomial size and polynomial degree can be reduced to O(log2n) depth (and even to O(logn) depth if unbounded-fanin gates are allowed). This establishes that OptLOGCFL is in AC1. This is the first depth-reduction result for arithmetic circuits over a non-commutative semiring, and it complements the lower bounds of Kosaraju and Nisan showing that depth reduction cannot be done in the general non-commutative 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 semiring (2∑∗, union, concat) in terms of simple one-way machines, and we investigate and extend earlier lower bounds on non-commutative circuits.