
Summary: Recent years have seen an increasing interest in the study of continuous-time computational models. However, not so much has been done with respect to setting up a complexity theoretic framework for such models. The present paper intends to go a step into this direction. We consider problems over the real numbers which we try to relate to Lyapunov theory for dynamical systems: The global minimizers of particular energy functions are supposed to give solutions of the problem. The structure of such energy functions leads to the introduction of problem classes \({\mathbf U}\) and \textbf{NU}; for the systems we are considering they parallel the classical complexity classes \({\mathbf P}\) and \textbf{NP}. We then introduce a notion of reducibility among problems and show existence of complete problems for \textbf{NU} and for \textbf{PU}, a polynomial hierarchy of continuous-time problems.
dynamical systems; analog computations; complexity; optimization, analog computation, Complexity classes (hierarchies, relations among complexity classes, etc.), Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Models of computation (Turing machines, etc.), Applications of dynamical systems, complexity, optimization, dynamical system, energy functions, 510, 004
dynamical systems; analog computations; complexity; optimization, analog computation, Complexity classes (hierarchies, relations among complexity classes, etc.), Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Models of computation (Turing machines, etc.), Applications of dynamical systems, complexity, optimization, dynamical system, energy functions, 510, 004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
