@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}
}

{"_id":"RjbJPyBCASXh47yan","bibbaseid":"siegelmann-sontag-analogcomputationvianeuralnetworks-1994","downloads":0,"creationDate":"2018-10-18T05:07:06.499Z","title":"Analog computation via neural networks","author_short":["Siegelmann, H. T.","Sontag, E."],"year":1994,"bibtype":"article","biburl":"http://www.sontaglab.org/PUBDIR/Biblio/complete-bibliography.bib","bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["H.","T."],"propositions":[],"lastnames":["Siegelmann"],"suffixes":[]},{"firstnames":["E.D."],"propositions":[],"lastnames":["Sontag"],"suffixes":[]}],"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","bibtex":"@ARTICLE{MR1288945,\n AUTHOR = {H. T. Siegelmann and E.D. Sontag},\n JOURNAL = {Theoret. Comput. Sci.},\n TITLE = {Analog computation via neural networks},\n YEAR = {1994},\n OPTMONTH = {},\n OPTNOTE = {},\n NUMBER = {2},\n PAGES = {331--360},\n VOLUME = {131},\n ADDRESS = {Essex, UK},\n KEYWORDS = {analog computing, neural networks, \n computational complexity, super-Turing computation, \n recurrent neural networks, neural networks, computational complexity},\n PUBLISHER = {Elsevier Science Publishers Ltd.},\n PDF = {../../FTPDIR/siegelmann_sontag_tcs1994.pdf},\n ABSTRACT = { We consider recurrent networks with real-valued \n weights. If allowed exponential time for computation, they turn out \n to have unbounded power. However, under polynomial-time constraints \n there are limits on their capabilities, though being more powerful \n than Turing Machines. Moreover, there is a precise correspondence \n between nets and standard non-uniform circuits with equivalent \n resources, and as a consequence one has lower bound constraints on \n what they can compute. We note that these networks are not likely to \n solve polynomially NP-hard problems, as the equality \"P=NP\" in our \n model implies the almost complete collapse of the standard polynomial \n hierarchy. We show that a large class of different networks and \n dynamical system models have no more computational power than this \n neural (first-order) model with real weights. The results suggest the \n following Church-like Thesis of Time-bounded Analog Computing: \"Any \n reasonable analog computer will have no more power (up to polynomial \n time) than first-order recurrent networks.\" },\n DOI = {http://dx.doi.org/10.1016/0304-3975(94)90178-3}\n}\n\n","author_short":["Siegelmann, H. T.","Sontag, E."],"key":"MR1288945","id":"MR1288945","bibbaseid":"siegelmann-sontag-analogcomputationvianeuralnetworks-1994","role":"author","urls":{},"keyword":["analog computing","neural networks","computational complexity","super-Turing computation","recurrent neural networks","neural networks","computational complexity"],"downloads":0,"html":""},"search_terms":["analog","computation","via","neural","networks","siegelmann","sontag"],"keywords":["analog computing","neural networks","computational complexity","super-turing computation","recurrent neural networks","neural networks","computational complexity"],"authorIDs":["5bc814f9db768e100000015a"],"dataSources":["DKqZbTmd7peqE4THw"]}