On ACC
On ACC
复制标题
在 ACC 上
DOI：
10.1007/bf01263423
复制
发表时间：
1994
影响因子：
1.4
通讯作者：
J. Tarui
中科院分区：
文献类型：
--
作者：
R. Beigel;J. Tarui
本文证明了ACC类中的每一种语言L都能被根上带有一个双函数门的深度为2的确定性电路识别，
$$2^{\log ^{O（1）} n} $$
扇入logO（1）n的与门，或者等价地，存在多项式spn（x1，.，xn）在Z上的次数为logO（1）n且系数为
时间复杂度O（1）
和函数shn：Z→{0，1}使得对于每个n和每个x ∈{0，1}n，XL（x）=hn（pn（x1，.，xn））。这改进了Yao（1985）的一个结果。我们还分析和改进了户田（1991）和姚（1985）构造的模放大多项式。
AbstractWe show that every languageL in the class ACC can be recognized by depth-two deterministic circuits with a symmetric-function gate at the root and
$$2^{\log ^{O(1)} n} $$
AND gates of fan-in logO(1)n at the leaves, or equivalently, there exist polynomialspn(x1,..., xn) overZ of degree logO(1)n and with coefficients of magnitude
$$2^{\log ^{O(1)} n} $$
and functionshn:Z→{0,1} such that for eachn and eachx∈{0,1}n,XL(x)=hn(pn(x1,...,xn)). This improves an earlier result of Yao (1985). We also analyze and improve modulus-amplifying polynomials constructed by Toda (1991) and Yao (1985).