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

DOI10.1145/3127496zbMath1426.68088arXiv1601.05360OpenAlexW2963290555MaRDI QIDQ4640346

Amaury Pouly, Olivier Bournez, Daniel Silva 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

computational complexityordinary differential equationscomputable analysisimplicit complexityanalog models of computationcontinuous-time models of computation

Mathematics Subject Classification ID

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

Related Items (11)

Characterizing time computational complexity classes with polynomial differential equations ⋮ Robust real-time computing with chemical reaction networks ⋮ 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 ⋮ On the stability of nucleic acid feedback control systems ⋮ A Universal Ordinary Differential Equation ⋮ Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations ⋮ Programming with ordinary differential equations: some first steps towards a programming language ⋮ A Survey on Analog Models of Computation

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