Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length

DOI10.1145/3127496MaRDI QIDQ4640346zbMATH OpenOpenAlexFDO

Authors Amaury Pouly, Olivier Bournez, Daniel Graça

Publication date 17 May 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.05360

zbMATH Keywords

analog models of computationcomputable analysiscomputational complexitycontinuous-time models of computationimplicit complexityordinary differential equations

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Nonlinear ordinary differential equations and systems (34A34) Other nonclassical models of computation (68Q09) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we characterize the class $operatornamePTIME$ of languages computable in polynomial time in terms of differential equations with polynomial right-hand side. This result gives a purely continuous (time and space) elegant and simple characterization of $operatornamePTIME$. This is the first time such 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. This extends to deterministic complexity classes above polynomial time. This may provide a new perspective on classical complexity, by giving a way to define complexity classes, like $operatornamePTIME$, 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, i.e.~by using the framework of analysis.

Recommendations

• Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length: the general purpose analog computer and computable analysis are two efficiently equivalent models of computations
• Polynomial solutions of a certain class of ordinary differential equations
• Characterizing time computational complexity classes with polynomial differential equations
• Polynomial solutions of certain classes of ordinary differential equations
• Polynomial solutions of differential-difference equations
• Polynomial solutions of certain differential equations
• Polynomial-time solution of initial value problems using polynomial enclosures
• scientific article; zbMATH DE number 2064551
• Polynomial solutions of differential equations
• On polynomial solutions of differential equations

Cited in

(26)

• A theory of complexity for continuous time systems
• Programming with ordinary differential equations: some first steps towards a programming language
• Robust real-time computing with chemical reaction networks
• On the stability of nucleic acid feedback control systems
• Computability with polynomial differential equations
• Computing with polynomial ordinary differential equations
• Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length: the general purpose analog computer and computable analysis are two efficiently equivalent models of computations
• A Survey on Analog Models of Computation
• Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations
• A universal ordinary differential equation
• A convenient expression of the time-derivative zn(k)(t) , of arbitrary order k, of the zero z _n (t) of a time-dependent polynomial p _N (z;t) of arbitrary degree N in z, and solvable dynamical systems
• Characterizing time computational complexity classes with polynomial differential equations
• Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines
• A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations
• \textit{CRN}++: molecular programming language
• A continuous characterization of PSPACE using polynomial ordinary differential equations
• Quantifiying the robustness of dynamical systems. Relating time and space to length and precision
• Biochemical relaxation oscillator designed to control molecular computation
• The complexity of computing in continuous time: space complexity is precision
• Solving discontinuous initial value problems with unique solutions is equivalent to computing over the transfinite
• Preparing Hamiltonians for quantum simulation: A computational framework for Cartan decomposition via Lax dynamics
• Rate-independent continuous inhibitory chemical reaction networks are Turing-universal
• Hydrodynamic and symbolic models of computation with advice
• Rate-independent computation in continuous chemical reaction networks
• Quantifying the robustness of dynamical systems. Relating time and space to length and precision
• A selective dual-railing technique for general-purpose analog computers

This page was built for publication: Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640346)