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

Neural Computation

September 1993, Vol. 5, No. 5, Pages 812-821
(doi: 10.1162/neco.1993.5.5.812)
© 1993 Massachusetts Institute of Technology
Attraction Radii in Binary Hopfield Nets are Hard to Compute
Article PDF (516.35 KB)
Abstract

We prove that it is an NP-hard problem to determine the attraction radius of a stable vector in a binary Hopfield memory network, and even that the attraction radius is hard to approximate. Under synchronous updating, the problems are already NP-hard for two-step attraction radii; direct (one-step) attraction radii can be computed in polynomial time.