Analog computation via neural networks*1

Hava T. Siegelmann,

Eduardo D. Sontag
Department of Mathematics and Computer Science, Bar-Ilan University, Ramat-gan, Israel
Department of Mathematics, Rutgers University, New Brunswick, NJ 08903, USA
Communicated by Eli Shamir Available online 2 April 2002.

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 the previous work (Siegelmann and Sontag, 1992).) Moreover, there is a precise correspondence between nets and standard nonuniform 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 “=” 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.

Theoretical Computer Science
Volume 131, Issue 2, 12 September 1994, Pages 331-360