Computability, Complexity and Programming with Ordinary Differential Equations - École polytechnique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Computability, Complexity and Programming with Ordinary Differential Equations

Résumé

Ordinary Differential Equations (ODEs) appear to be a universally adopted and very natural way for expressing properties for continuous time dynamical systems. They are intensively used, in particular in applied sciences. There exists an abundant literature about the hardness of solving ODEs with numerical methods. We adopt a dual view: we consider ODEs as a way to program or to describe our mathematical/computer science world. We survey several results considering ODEs under this computational perspective, with a computability and complexity theory point of view. In particular, we provide various reasons why polynomial ODEs should be considered as the continuous time analog of Turing machines for continuous-time computations, or should be used as a way to talk about mathematical logic. This has already applications in various fields: determining whether analog models of computation can compute faster than classical digital models of computation; solving complexity issues for computations with biochemical reactions in bioinformatics; machine independent characterizations of various computability and complexity classes such as PTIME or NPTIME, or proof of the existence of a universal polynomial ordinary differential equation whose solutions can approximate any continuous function if provided with a suitable well-chosen initial condition.
Fichier principal
Vignette du fichier
LIPIcs-STACS-2020-3.pdf (580.79 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-03668004 , version 1 (13-05-2022)

Identifiants

Citer

Olivier Bournez. Computability, Complexity and Programming with Ordinary Differential Equations. 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, Montpellier, France. ⟨10.4230/LIPIcs.STACS.2020.3⟩. ⟨hal-03668004⟩
21 Consultations
34 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More