ML Anthology

Attraction Radii in Binary Hopfield Nets Are Hard to Compute

Patrik Floréen, Pekka Orponen
NeCo 1993 pp. 812-821
doi:10.1162/NECO.1993.5.5.812 /neco/1993/floreen1993neco-attraction/

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.

PDF NeCo Semantic Scholar

Cite

Text

Floréen and Orponen. "Attraction Radii in Binary Hopfield Nets Are Hard to Compute." Neural Computation, 1993. doi:10.1162/NECO.1993.5.5.812

Markdown

[Floréen and Orponen. "Attraction Radii in Binary Hopfield Nets Are Hard to Compute." Neural Computation, 1993.](https://mlanthology.org/neco/1993/floreen1993neco-attraction/) doi:10.1162/NECO.1993.5.5.812

BibTeX

@article{floreen1993neco-attraction,
  title     = {{Attraction Radii in Binary Hopfield Nets Are Hard to Compute}},
  author    = {Floréen, Patrik and Orponen, Pekka},
  journal   = {Neural Computation},
  year      = {1993},
  pages     = {812-821},
  doi       = {10.1162/NECO.1993.5.5.812},
  volume    = {5},
  url       = {https://mlanthology.org/neco/1993/floreen1993neco-attraction/}
}