A note on the power of threshold circuits
A note on the power of threshold circuits
复制标题
关于阈值电路功率的说明
DOI：
10.1109/sfcs.1989.63538
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
Eric Allender
中科院分区：
文献类型：
--
作者：
Eric Allender
作者提供了一个非常简单的证明，证明了以多项式大小的深度-K接收到的任何语言和 / / / / / / / /或大门接受的任何语言都被深度三个阈值n的阈值n升高到功率o（log o（log） /sup k/n）。该证据使用了S. toda结果的大部分直觉，即多项式层次结构包含在p/ sup hash p/ p/ p/ p/ p/semp。Symp。Sci.Sci。，P.514-519，1989）中。<< Etx> >
The author presents a very simple proof of the fact that any language accepted by polynomial-size depth-k unbounded-fan-in circuits of AND and OR gates is accepted by depth-three threshold circuits of size n raised to the power O(log/sup k/n). The proof uses much of the intuition of S. Toda's result that the polynomial hierarchy is contained in P/sup Hash P/ (30th Ann. Symp. Foundations Comput. Sci., p.514-519, 1989).<<ETX>>