ANALOG COMPUTATION WITH DYNAMICAL-SYSTEMS

Physical systems exhibit various levels of complexity: their long term dynamics may converge to fixed points or exhibit complex chaotic beha vior. This paper presents a theory that enables to interpret natural p rocesses as special purpose analog computers. Since physical systems a re naturally described in continuous time, a definition of computation al complexity for continuous time systems is required. In analogy with the classical discrete theory we develop fundamentals of computationa l complexity for dynamical systems, discrete or continuous in time, on the basis of an intrinsic time scale of the system. Dissipative dynam ical systems are classified into the computational complexity classes P-d, Co-RPd, NPd and EXPd, corresponding to their standard counterpart s, according to the complexity of their long term behavior. The comple xity of chaotic attractors relative to regular ones leads to the conje cture P-d not equal NPd. Continuous time flows have been proven useful in solving various practical problems. Our theory provides the tools for an algorithmic analysis of such flows. As an example we analyze th e continuous Hopfield network. (C) 1998 Elsevier Science B.V. All righ ts reserved.