Monthly
288 pp. per issue
6 x 9, illustrated
ISSN
0899-7667
E-ISSN
1530-888X
2014 Impact factor:
2.21

Neural Computation

February 15, 1996, Vol. 8, No. 2, Pages 403-415
(doi: 10.1162/neco.1996.8.2.403)
© 1996 Massachusetts Institute of Technology
The Computational Power of Discrete Hopfield Nets with Hidden Units
Article PDF (685.81 KB)
Abstract

We prove that polynomial size discrete Hopfield networks with hidden units compute exactly the class of Boolean functions PSPACE/poly, i.e., the same functions as are computed by polynomial space-bounded nonuniform Turing machines. As a corollary to the construction, we observe also that networks with polynomially bounded interconnection weights compute exactly the class of functions P/poly, i.e., the class computed by polynomial time-bounded nonuniform Turing machines.