The outcomes of this paper are twofold. Implicit complexity. We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we characterize the class PTIME of languages computable in polynomial time in terms of differential equations with polynomial right-hand side. This result gives a purely continuous elegant and simple characterization of PTIME. We believe it is the first time complexity classes are characterized using only ordinary differential equations. Our characterization extends to functions computable in polynomial time over the reals in the sense of computable analysis. Our results may provide a new perspective on classical complexity, by giving a way to define complexity classes, like PTIME, in a very simple way, without any reference to a notion of (discrete) machine. This may also provide ways to state classical questions about computational complexity via ordinary differential equations. Continuous-Time Models of Computation. Our results can also be interpreted in terms of analog computers or analog models of computation: As a side effect, we get that the 1941 General Purpose Analog Computer (GPAC) of Claude Shannon is provably equivalent to Turing machines both in terms of computability and complexity, a fact that has never been established before. This result provides arguments in favour of a generalised form of the Church-Turing Hypothesis, which states that any physically realistic (macroscopic) computer is equivalent to Turing machines both in terms of computability and complexity.
Attempts to derive a complexity theory for continuous-time systems include @cite_20 . However, the theory developed there is not intended to cover generic dynamical systems but only specific systems that are related 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 @math and @math , with the existence of complete problems for theses classes.
@cite_20
2041768209 2893838930 2152556309 2130154921
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 U and NU; for the systems we are considering they parallel the classical complexity classes P and NP. We then introduce a notion of reducibility among problems and show existence of complete problems for NU and for PU, a polynomial hierarchy of continuous-time problems. For previous work on the computational capabilities of continuous-time systems see the surveys by Cris Moore [9] and by Pekka Orponen [10]. Our paper presents a step into the direction of creating a general framework for a complexity theory of continuous-time systems as outlined in [10]. It is closely related to work done by A. Ben-Hur, H. Siegelmann, and S. Fishman [12, 11]. Author(s): Wilson, Ashia | Advisor(s): Jordan, Michael I; Recht, Benjamin | Abstract: Optimization is among the richest modeling languages in science. In statistics and machine learning, for instance, inference is typically posed as an optimization problem. While there are many algorithms designed to solve optimization problems, and a seemingly greater number of convergence proofs, essentially all proofs follow a classical approach from dynamical systems theory: they present a Lyapunov function and show it decreases. The primary goal of this thesis is to demonstrate that making the Lyapunov argument explicit greatly simplifies, clarifies, and to a certain extent, unifies, convergence theory for optimization.The central contributions of this thesis are the following results: we• present several variational principles whereby we obtain continuous-time dynamical systems useful for optimization;• introduce Lyapunov functions for both the continuous-time dynamical systems and discrete-time algorithms and demonstrate how to move between these Lyapunov functions;• utilize the Lyapunov framework as well as numerical analysis and integration techniques to obtain upper bounds for several novel discrete-time methods for optimization, a few of which have matching lower bounds. This paper proposes a design methodology to stabilize isolated relative equilibria in a model of all-to-all coupled identical particles moving in the plane at unit speed. Isolated relative equilibria correspond to either parallel motion of all particles with fixed relative spacing or to circular motion of all particles with fixed relative phases. The stabilizing feedbacks derive from Lyapunov functions that prove exponential stability and suggest almost global convergence properties. The results of the paper provide a low-order parametric family of stabilizable collectives that offer a set of primitives for the design of higher-level tasks at the group level We deal with nonlinear dynamical systems, consisting of a linear nominal part perturbed by model uncertainties, nonlinearities and both additive and multiplicative random noise, modeled as a Wiener process. In particular, we study the problem of finding suitable measurement feedback control laws such that the resulting closed-loop system is stable in some probabilistic sense. To this aim, we introduce a new notion of stabilization in probability, which is the natural counterpart of the classical concept of regional stabilization for deterministic nonlinear dynamical systems and stands as an intermediate notion between local and global stabilization in probability. This notion requires that, given a target set, a trajectory, starting from some compact region of the state space containing the target, remains forever inside some larger compact set, eventually enters any given neighborhood of the target in finite time and remains thereinafter, all these events being guaranteed with some probability. We give a Lyapunov-based sufficient condition for achieving stability in probability and a separation result which splits the control design into a state feedback problem and a filtering problem. Finally, we point out constructive procedures for solving the state feedback and filtering problem with arbitrarily large region of attraction and arbitrarily small target for a wide class of nonlinear systems, which at least include feedback linearizable systems. The generality of the result is promising for applications to other classes of stochastic nonlinear systems. In the deterministic case, our results recover classical stabilization results for nonlinear systems.