HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Síma, J. Articles by Antti-Poika, T. Search for Related Content PubMed PubMed Citation Articles by Síma, J. Articles by Antti-Poika, T.

On the Computational Complexity of Binary and Analog Symmetric Hopfield Nets

Jií íma

Department of Theoretical Computer Science, Institute of Computer Science, Academy of Sciences of the Czech Republic, P.O. Box 5, 182 07 Prague 8, Czech Republic

Pekka Orponen

Department of Mathematics, University of Jyväskylä, FIN-40351 Jyväskylä, Finland

Teemu Antti-Poika

Department of Mathematics, University of Jyväskylä, FIN-40351 Jyväskylä, Finland

We investigate the computational properties of finite binary- and analog-state discrete-time symmetric Hopfield nets. For binary networks, we obtain a simulation of convergent asymmetric networks by symmetric networks with only a linear increase in network size and computation time. Then we analyze the convergence time of Hopfield nets in terms of the length of their bit representations. Here we construct an analog symmetric network whose convergence time exceeds the convergence time of any binary Hopfield net with the same representation length. Further, we prove that the MIN ENERGY problem for analog Hopfield nets is NP-hard and provide a polynomial time approximation algorithm for this problem in the case of binary nets. Finally, we show that symmetric analog nets with an external clock are computationally Turing universal.

This article has been cited by other articles:

				J. Sima and P. Orponen General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results Neural Comput., December 1, 2003; 15(12): 2727 - 2778. [Abstract] [Full Text] [PDF]

				J. Sima and P. Orponen Continuous-Time Symmetric Hopfield Nets Are Computationally Universal Neural Comput., March 1, 2003; 15(3): 693 - 733. [Abstract] [Full Text] [PDF]