Skip to main content
Article
Computational Complexity for Continuous Time Dynamics
Physical Review Letters (1999)
  • Hava Siegelmann, University of Massachusetts - Amherst
  • Asa Ben-Hur
  • Shmuel Fishman
Abstract
Dissipative flows model a large variety of physical systems. In this Letter the evolution of such systems is interpreted as a process of computation; the attractor of the dynamics represents the output. A framework for an algorithmic analysis of dissipative flows is presented, enabling the comparison of the performance of discrete and continuous time analog computation models. A simple algorithm for finding the maximum of n numbers is analyzed, and shown to be highly efficient. The notion of tractable (polynomial) computation in the Turing model is conjectured to correspond to computation with tractable (analytically solvable) dynamical systems having polynomial complexity.
Disciplines
Publication Date
August 16, 1999
Publisher Statement
DOI: 10.1103/PhysRevLett.83.1463
Citation Information
Hava Siegelmann, Asa Ben-Hur and Shmuel Fishman. "Computational Complexity for Continuous Time Dynamics" Physical Review Letters Vol. 83 Iss. 7 (1999)
Available at: http://works.bepress.com/hava_siegelmann/11/