doi abstract bibtex

We consider recurrent networks with real-valued weights. 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. 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. 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. We show that a large class of different networks and dynamical system models have no more computational power than this neural (first-order) model with real weights. The results suggest the following Church-like Thesis of Time-bounded Analog Computing: "Any reasonable analog computer will have no more power (up to polynomial time) than first-order recurrent networks."

@ARTICLE{MR1288945, AUTHOR = {H. T. Siegelmann and E.D. Sontag}, JOURNAL = {Theoret. Comput. Sci.}, TITLE = {Analog computation via neural networks}, YEAR = {1994}, OPTMONTH = {}, OPTNOTE = {}, NUMBER = {2}, PAGES = {331--360}, VOLUME = {131}, ADDRESS = {Essex, UK}, KEYWORDS = {analog computing, neural networks, computational complexity, super-Turing computation, recurrent neural networks, neural networks, computational complexity}, PUBLISHER = {Elsevier Science Publishers Ltd.}, PDF = {../../FTPDIR/siegelmann_sontag_tcs1994.pdf}, ABSTRACT = { We consider recurrent networks with real-valued weights. 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. 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. 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. We show that a large class of different networks and dynamical system models have no more computational power than this neural (first-order) model with real weights. The results suggest the following Church-like Thesis of Time-bounded Analog Computing: "Any reasonable analog computer will have no more power (up to polynomial time) than first-order recurrent networks." }, DOI = {http://dx.doi.org/10.1016/0304-3975(94)90178-3} }

Downloads: 0