NeuroCOLT

Neural Networks and Computational Learning Theory

About NeuroCOLT

Papers Archive

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-94-009

Complexity Issues in Discrete Hopfield Networks

Patrik Floréen and Pekka Orponen
University of Helsinki
Department of Computer Science
P. O. Box 26, FIN-00014 University of Helsinki
Finland

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.

Download Compressed Postscript