A theory of complexity for continuous time systems

被引：24

作者：

Ben-Hur, A

Siegelmann, HT

Fishman, S

机构：

[1] Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel

[2] MIT, Informat & Decis Syst Lab, Cambridge, MA 02139 USA

[3] Technion Israel Inst Technol, Dept Phys, IL-32000 Haifa, Israel

来源：

JOURNAL OF COMPLEXITY | 2002年 / 18卷 / 01期

关键词：

theory of analog computation; dynamical systems;

D O I：

10.1006/jcom.2001.0581

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2001 Elsevier Science (USA).

引用

页码：51 / 86

页数：36