Complex Systems

On the Computational Complexity of Analyzing Hopfield Nets Download PDF

Patrik Floréen
Pekka Orponen
Department of Computer Science, University of Helsinki,
SF--00510 Helsinki, Finland


We prove that the problem of counting the number of stable states in a given Hopfield net is #P-complete and the problem of computing the size of the attraction domain of a given stable state is NP-hard.