Computation by dynamical systems
Hava T. Siegelmann, Shmuel Fishman · 2002
A theory for computation by dynamical systems is presented, definition of computation time that is applicable for systems that are continuous as well as for systems that are discrete in time, based on a physical time scale is introduced. Computational complexity of dynamical systems is explored. For this purpose the standard classes of computer science are adapted to dynamical systems. The complexity classes P/sub d/, BPP/sub d/ and NP/sub d/ corresponding to the standard classes P, BPP and NP are defined for the case of more physical dynamics. It is then shown that computation of a simple fixed point is in P/sub d/ or BPP/sub d/ (depending on the output decision process) while for an isolated strange attractor it is in NP/sub d/. The computation by the continuous Hopfield neural network is analyzed in detail and found to be in P/sub d/ or in BPP/sub d/.