Computational complexity for continuous-time dynamics

Hava T. Siegelmann; Asa Ben-Hur; Shmuel Fishman

doi:10.1117/12.409210

17 November 2000 Computational complexity for continuous-time dynamics

Hava T. Siegelmann, Asa Ben-Hur, Shmuel Fishman

Proceedings Volume 4109, Critical Technologies for the Future of Computing; (2000) https://doi.org/10.1117/12.409210
Event: International Symposium on Optical Science and Technology, 2000, San Diego, CA, United States

Abstract

We present a model of computation with ordinary differential equations (ODEs) which converge to attractors that are interpreted as the output of a computation. We introduce a measure of complexity for exponentially convergent ODEs, enabling an algorithmic analysis of continuous time flows and their comparison with discrete algorithms. We define polynomial and logarithmic continuous time complexity classes and show that an ODE which solves the maximum network flow problem has polynomial time complexity. We also analyze a simple flow that solves the maximum problem in logarithmic time. We conjecture that a subclass of the continuous P is equivalent to the classical P.

Citation Download Citation

Hava T. Siegelmann, Asa Ben-Hur, and Shmuel Fishman "Computational complexity for continuous-time dynamics", Proc. SPIE 4109, Critical Technologies for the Future of Computing, (17 November 2000); https://doi.org/10.1117/12.409210

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available