Computing Algebraic Formulas Using a Constant Number of Registers
Computing Algebraic Formulas Using a Constant Number of Registers
复制标题
使用恒定数量的寄存器计算代数公式
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
R. Cleve
中科院分区：
文献类型：
--
作者：
M. Ben;R. Cleve
结果表明，在任意环上，由多项式长度代数公式计算的函数也可由仅使用三个寄存器的多项式长度代数直线程序计算。这以前因布尔公式而闻名[D. A. Barrington，J. 计算机。 System Sci., 38 (1989), pp. 150–164]，这相当于环 $GF(2)$ 上的代数公式。对于任意环上的公式，结果比以前的方法有所改进，以前的方法要求寄存器的数量与公式的大小成对数，以获得多项式长度的直线程序。此外，在这些结构中出现的直线程序具有这样的属性：它们由对寄存器的操作是线性和双射的语句组成。其结果是，对于代数 $NC^1 $，确定 $n3 imes 3$ 矩阵的迭代积的问题是完整的（在 P 投影下）。另外，当环为 $GF(2)$ 时，c 中出现的程序...
It is shown that, over an arbitrary ring, the functions computed by polynomial-size algebraic formulas are also computed by polynomial-length algebraic straight-line programs that use only three registers. This was previously known for Boolean formulas [D. A. Barrington, J. Comput. System Sci., 38 (1989), pp. 150–164], which are equivalent to algebraic formulas over the ring $GF(2)$. For formulas over arbitrary rings, the result is an improvement over previous methods that require the number of registers to be logarithmic in the size of the formulas in order to obtain polynomial-length straight-line programs. Moreover, the straight-line programs that arise in these constructions have the property that they consist of statements whose actions on the registers are linear and bijective. A consequence of this is that the problem of determining the iterated product of $n3 imes 3$ matrices is complete (under P-projections) for algebraic $NC^1 $. Also, when the ring is $GF(2)$, the programs that arise in the c...