3 reports available

[Patrik Floreen]

The following 3 reports are now available:

  "Attraction Radii in Binary Hopfield Nets are Hard to Compute"
  by Patrik Floreen and Pekka Orponen, University of Helsinki.
  The name of the file is floreen.attrrad.ps.Z
         
  "Neural Networks and Complexity Theory"
  by Pekka Orponen, University of Helsinki.
  The name of the file is orponen.nncomp.ps.Z

  "On the Computational Power of Discrete Hopfield Nets"
  by Pekka Orponen, University of Helsinki.
  The name of the file is orponen.hoppow.ps.Z
 
------------

Abstracts of the papers:

"Attraction Radii in Binary Hopfield Nets are Hard to Compute"
ABSTRACT: We prove that it is an NP-hard problem to determine the attraction
radius of a stable vector in a binary Hopfield memory network, and even that 
the attraction radius is hard to approximate. Under synchronous updating, 
the problems are already NP-hard for two-step attraction radii;
direct (one-step) attraction radii can be computed in polynomial time.

"Neural Networks and Complexity Theory"
ABSTRACT: We survey some of the central results in the complexity theory of 
discrete neural networks, with pointers to the literature.

"On the Computational Power of Discrete Hopfield Nets"
ABSTRACT: We prove that polynomial size discrete synchronous Hopfield networks
with hidden units compute exactly the class of Boolean functions PSPACE/poly, 
i.e., the same functions as are computed by polynomial space-bounded nonuniform 
Turing machines. As a corollary to the construction, we observe also that 
networks with polynomially bounded interconnection weights compute exactly the 
class of functions P/poly.

---------------------------------------------------------------------------
To obtain copies of the postscript files, please use Jordan Pollack's service:

Example:
unix> ftp cheops.cis.ohio-state.edu          # (or ftp 128.146.8.62)
Name (cheops.cis.ohio-state.edu:): anonymous
Password (cheops.cis.ohio-state.edu:anonymous): <ret>
ftp> cd pub/neuroprose
ftp> binary
ftp> get
(remote-file) floreen.attrrad.ps.Z
(local-file) foo.ps.Z
ftp> quit
unix> uncompress foo.ps
unix> lpr -P(your_local_postscript_printer) foo.ps

Likewise for orponen.hoppow.ps.Z and orponen.nncomp.ps.Z

----------------------------------------------------------------------------
If you have any difficulties with the above, please send e-mail to
floreen at cs.helsinki.fi.  DO NOT "reply" to this message, please.