Analog computation via neural networks. Siegelmann, H. T. and Sontag, E. Theoret. Comput. Sci., 131(2):331–360, Elsevier Science Publishers Ltd., Essex, UK, 1994.
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