Paper on Neuroprose: Complexity Issues in Discrete Hopfield Networks

[Patrik Floreen]

FTP-host: archive.cis.ohio-state.edu
FTP-file: pub/neuroprose/floreen.hopfield.ps.Z

-------------------------------------------------------------

The following paper has been placed in the Neuroprose archive at 
Ohio State University: 

P. Floreen and P. Orponen: 
Complexity Issues in Discrete Hopfield Networks (55 pages)

Patrik Floreen
Department of Computer Science
P.O.Box 26 (Teollisuuskatu 23)
FIN-00014 University of Helsinki
floreen at cs.helsinki.fi


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.

The text is a draft chapter for the forthcoming book "The Computational
and Learning Complexity of Neural Networks: Advanced Topics" (ed. Ian Parberry).

Instructions for ftp retrieval of this paper are given below.  
Please do not reply directly to this message.

FTP INSTRUCTIONS:

unix> ftp archive.cis.ohio-state.edu (or 128.146.8.52)
    Name: anonymous
    Password: <your e-mail address>
    ftp> cd pub/neuroprose
    ftp> binary
    ftp> get floreen.hopfield.ps.Z
    ftp> quit
unix> uncompress floreen.hopfield.ps.Z

Thanks to Jordan Pollack for maintaining this archive. 

Patrik Floreen