Name
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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1006/jcom.2001.0581 | J. Complexity |
Keywords | DocType | Volume |
continuous time system,logarithmic time,theory of analog computation,dynamical systems,algorithmic analysis,dynamical systems.,continuous P,simple flow,continuous time flow,polynomial time complexity,maximum network flow problem,logarithmic continuous time complexity,Maximum problem,exponentially convergent ODEs | Journal | 18 |
Issue | ISSN | Citations |
1 | Journal of Complexity | 20 |
PageRank | References | Authors |
1.20 | 16 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Asa Ben-Hur | 1 | 1405 | 110.73 |
| Hava T. Siegelmann | 2 | 980 | 145.09 |
| Shmuel Fishman | 3 | 28 | 4.40 |