"Neural networks with real weights: analog computational complexity"

[Eduardo Sontag]

Title: "Neural networks with real weights: analog computational complexity"
Authors: Hava T. Siegelmann and Eduardo D. Sontag

(Report SYCON 92-05, September 1992. 24 + i pp.)
(Placed in neuroprose archive; filename: siegelmann.analog.ps.Z)

Abstract:

We pursue a particular approach to analog computation, based on dynamical
systems of the type used in neural networks research.
Our systems have a fixed structure, invariant in time, corresponding to an
unchanging number of ``neurons''.  If allowed exponential time for
computation, they turn out to have unbounded power.  However, under
polynomial-time constraints there are limits on their capabilities, though
being more powerful than Turing Machines.  (A similar but more restricted
model was shown to be polynomial-time equivalent to classical digital
computation in previous work.)  Moreover, there is a precise correspondence
between nets and standard non-uniform circuits with equivalent resources, and
as a consequence one has lower bound constraints on what they can compute.
This relationship is perhaps surprising since our analog devices do not change
in any manner with input size.

We note that these networks are not likely to solve polynomially NP-hard
problems, as the equality ``P = NP'' in our model implies the almost complete
collapse of the standard polynomial hierarchy.

In contrast to classical computational models, the models studied here exhibit
at least some robustness with respect to noise and implementation errors.

To obtain copies of this article:

unix> ftp archive.cis.ohio-state.edu (or 128.146.8.52)
Name : anonymous
Password: <your id>
ftp> cd pub/neuroprose
ftp> binary
ftp> get siegelmann.analog.ps.Z
ftp> quit
unix> uncompress siegelmann.analog.ps.Z
unix> lpr -Pps siegelmann.analog.ps.Z (or however you print PostScript)

(With many thanks to Jordan Pollack for providing this valuable service!)

Please note: the file requires a fair amount of memory to print.
If you have problems with FTP, I can e-mail you the postscript file; I cannot
provide hardcopy, however.