Analog computation via neural networks
Hava T. Siegelmann, Eduardo D. Sontag · 2002
The authors pursue a particular approach to analog computation, based on dynamical systems of the type used in neural networks research. The 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. These networks are not likely to solve polynomially-NP-hard problems, as the equality 'P=NP' implies the almost complete collapse of the standard polynomial hierarchy. In contrast to classical computational models, the models studied exhibit at least some robustness with respect to noise and implementation errors.>