Neural Computation
February 15, 1996, Vol. 8, No. 2, Pages 403-415
(doi: 10.1162/neco.1996.8.2.403)
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.