ANALOG COMPUTATION VIA NEURAL NETWORKS

We pursue a particular approach to analog computation, based on dynami cal systems of the type used in neural networks research. Our systems have a fixed structure, invariant in time, corresponding to an unchang ing 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 wa s shown to be polynomial-time equivalent to classical digital computat ion in the previous work (Siegelmann and Sontag, 1992).) Moreover, the re is a precise correspondence between nets and standard nonuniform ci rcuits with equivalent resources, and as a consequence one has lower b ound constraints on what they can compute. This relationship is perhap s surprising since our analog devices do not change in any manner with input size. We note that these networks are not likely to solve polyn omially NP-hard problems, as the equality ''P=NP'' in our model implie s the almost complete collapse of the standard polynomial hierarchy. I n contrast to classical computational models, the models studied here exhibit at least some robustness with respect to noise and implementat ion errors.