Share Email Print

Proceedings Paper

Computational complexity for continuous-time dynamics
Author(s): Hava T. Siegelmann; Asa Ben-Hur; Shmuel Fishman
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 17 November 2000
PDF: 11 pages
Proc. SPIE 4109, Critical Technologies for the Future of Computing, (17 November 2000); doi: 10.1117/12.409210
Show Author Affiliations
Hava T. Siegelmann, Technion-Israel Institute of Technology (Israel)
Asa Ben-Hur, Technion-Israel Institute of Technology (Israel)
Shmuel Fishman, Technion-Israel Institute of Technology (Israel)

Published in SPIE Proceedings Vol. 4109:
Critical Technologies for the Future of Computing
Sunny Bains; Leo J. Irakliotis, Editor(s)

© SPIE. Terms of Use
Back to Top