Title :
A note on the power of threshold circuits
Author_Institution :
Dept. of Comput. Sci., Rutgers Univ., New Brunswick, NJ, USA
fDate :
30 Oct-1 Nov 1989
Abstract :
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(logk n). The proof uses much of the intuition of S. Toda´s result that the polynomial hierarchy is contained in P#P (30th Ann. Symp. Foundations Comput. Sci., p.514-519, 1989)
Keywords :
switching theory; threshold logic; AND gates; OR gates; depth-three threshold circuits; polynomial hierarchy; threshold circuits; unbounded-fan-in circuits; Circuit simulation; Computational modeling; Computer science; Out of order; Polynomials;
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
DOI :
10.1109/SFCS.1989.63538
