NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/comp/theory/2737

Internet Message Format | 1992-12-21 | 3.7 KB

Path: sparky!uunet!dtix!darwin.sura.net!jvnc.net!rutgers!igor.rutgers.edu!control.rutgers.edu!sontag
From: [e-mail] (Eduardo Sontag)
Newsgroups: comp.theory
Subject: Re: Real Numbers vs. Rational Numbers?
Message-ID: <[e-mail]>
Date: 20 Dec 92 21:19:09 GMT
References: <[e-mail]> <[e-mail]>
Reply-To: [e-mail]
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 73
In-Reply-To: [e-mail]'s message of 17 Dec 92 10:45:02 GMT

In article <[e-mail]> [e-mail] (Claude Diderich) writes:

   I asked myself some time ago the same question (e.g. are Turing machines
   computing on real numbers equvalent on ones computing only on rationals),
   but I
   was unable to find any answer. I was especially intersted in complexity
   theoretical results. Any pointers in the literature about real vs. rational
   vouls be highly appreciated.

In recent work (under review, but available electronically, see below), we
show there is a precise equivalence between a model of real-number computation
("recurrent neural nets" operating under polynomial time constraints) and a
precise non-Turing complexity class (Turing machines that consult sparse
oracles).  From this, we can deduce a number of upper bounds on the
computational capabilities of such "analog computers".

You can FTP the file.  Details follow:

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.
--
Eduardo D. Sontag
Department of Mathematics
Rutgers Center for Systems and Control (SYCON)
Rutgers University
New Brunswick, NJ 08903, USA

(Phone: [phone]; FAX: [phone])
[e-mail]