DocumentCode
2892967
Title
On the computational power of sigmoid versus Boolean threshold circuits
Author
Maass, Wolfgang ; Schnitger, Georg ; Sontag, Eduardo D.
Author_Institution
Inst. for Inf. Process. Graz, Graz Univ. of Technol., Austria
fYear
1991
fDate
1-4 Oct 1991
Firstpage
767
Lastpage
776
Abstract
The power of constant depth circuits with sigmoid (i.e., smooth) threshold gates for computing Boolean functions is examined. It is shown that, for depth 2, constant size circuits of this type are strictly more powerful than constant size Boolean threshold circuits (i.e., circuits with Boolean threshold gates). On the other hand it turns out that, for any constant depth d , polynomial size sigmoid threshold circuits with polynomially bounded weights compute exactly the same Boolean functions as the corresponding circuits with Boolean threshold gates
Keywords
Boolean functions; computational complexity; logic circuits; logic gates; neural nets; threshold logic; Boolean functions; Boolean threshold circuits; Boolean threshold gates; computational power; constant depth circuits; constant size circuits; depth 2 circuits; polynomial size sigmoid threshold circuits; polynomially bounded weights; sigmoid threshold gates; smooth threshold gates; Analog computers; Boolean functions; Circuits; Computational modeling; Computer networks; Concurrent computing; Information processing; Neural networks; Neurons; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Conference_Location
San Juan
Print_ISBN
0-8186-2445-0
Type
conf
DOI
10.1109/SFCS.1991.185447
Filename
185447
Link To Document