|Ph.D Student||Ben Hur Asa|
|Subject||Computation: A Dynamical Systems Approach|
|Department||Department of Industrial Engineering and Management||Supervisor||Ms. Hava Sigelmann|
The theory of complexity, one of the cornerstones of theoretical computer science, has logic and discrete mathematics as its mathematical foundations. In its basis is the Turing machine, the mathematical abstraction of a digital computer. A Turing machine is essentially a discrete time dynamical systems in a discrete configuration space. In this thesis we aim to incorporate concepts of mathematical analysis into complexity theory, thus enlarging its scope to encompass continuous algorithms defined by differential equations. We provide the foundations for an algorithmic and complexity analysis of flows that converge to fixed points. This way the efficiency of a large class of continuous algorithms defined by differential equations can be compared against discrete algorithms.
Time complexity of continuous time systems is a delicate issue that is hard to define in a meaningful way. By interpreting differential equations as models of physical systems we connect time as measured in the laboratory with time complexity, making it a well-defined concept. We show that a differential equation that solves the maximum network flow problem has polynomial (continuous) time complexity, and perform a probabilistic analysis of a flow for linear programming. We conjecture that a subclass of the continuous P is equivalent to the classical P.
Considering ODEs in computational terms allows a computational interpretation of physical and biological phenomena. As an example, we analyze a set of equations that describe the process of gene expression in a cell. New experiments that report the construction of artificial gene networks suggest that this might be useful as a novel computing paradigm.