Complexity Issues in Discrete Hopfield Networks

Patrik Floréen, and Pekka Orponen: Complexity Issues in Discrete Hopfield Networks. Report A-1994-4, Department of Computer Science, University of Helsinki, 1994. 54 pages. <http://www.cs.helsinki.fi/TR/A-1994/4>

Full paper: gzip'ed Postscript file
Metadata: XML file

Abstract

We survey some aspects of the computational complexity theory of discrete-time and discrete-state Hopfield networks. The emphasis is on topics that are not adequately covered by the existing survey literature, most significantly:

1. the known upper and lower bounds for the convergence times of Hopfield nets (here we consider mainly worst­case results);
2. the power of Hopfield nets as general computing devices (as opposed to their applications to associative memory and optimization);
3. the complexity of the synthesis (``learning'') and analysis problems related to Hopfield nets as associative memories.

Index Terms

Categories and Subject Descriptors:
B.3.2, C.1.3, F.1.1, F.1.3

General Terms:

Additional Key Words and Phrases: