ON ACC and threshold circuits
ON ACC and threshold circuits
复制标题
ON ACC 和阈值电路
DOI：
10.1109/fscs.1990.89583
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
A. Yao
中科院分区：
文献类型：
--
作者：
A. Yao
证明，ACC中的任何语言都可以通过凸起的2级电路计算到（log n）/ sup k/ power的两级电路，在顶部，唯一的对称功能门，在第一级上，大门。这意味着ACC中的任何语言都可以通过该大小的Depth-3阈值电路识别。该结果给出了ACC电路的计算能力的第一个非平凡的上限。<< etx >>
It is proved that any language in ACC can be approximately computed by two-level circuits of size 2 raised to the (log n)/sup k/ power, with a symmetric-function gate at the top and only AND gates on the first level. This implies that any language in ACC can be recognized by depth-3 threshold circuits of that size. This result gives the first nontrivial upper bound on the computing power of ACC circuits.<<ETX>>