Complexity Theory meets Ordinary Differential Equations
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911584491667456 |
|---|---|
| author | Fono, Adalbert Wedlich, Noah Boche, Holger Kutyniok, Gitta |
| author_facet | Fono, Adalbert Wedlich, Noah Boche, Holger Kutyniok, Gitta |
| contents | This contribution investigates the computational complexity of simulating linear ordinary differential equations (ODEs) on digital computers. We provide an exact characterization of the complexity blowup for a class of ODEs of arbitrary order based on their algebraic properties, extending previous characterization of first order ODEs. Complexity blowup indeed arises in most ODEs (except for certain degenerate cases) and means that there exists a low complexity input signal, which can be generated on a Turing machine in polynomial time, leading to a corresponding high complexity output signal of the system in the sense that the computation time for determining an approximation up to $n$ significant digits grows faster than any polynomial in $n$. Similarly, we derive an analogous blowup criterion for a subclass of first-order systems of linear ODEs. Finally, we discuss the implications for the simulation of analog systems governed by ODEs and exemplarily apply our framework to a simple model of neuronal dynamics$-$the leaky integrate-and-fire neuron$-$heavily employed in neuroscience. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_09790 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Complexity Theory meets Ordinary Differential Equations Fono, Adalbert Wedlich, Noah Boche, Holger Kutyniok, Gitta Computational Complexity This contribution investigates the computational complexity of simulating linear ordinary differential equations (ODEs) on digital computers. We provide an exact characterization of the complexity blowup for a class of ODEs of arbitrary order based on their algebraic properties, extending previous characterization of first order ODEs. Complexity blowup indeed arises in most ODEs (except for certain degenerate cases) and means that there exists a low complexity input signal, which can be generated on a Turing machine in polynomial time, leading to a corresponding high complexity output signal of the system in the sense that the computation time for determining an approximation up to $n$ significant digits grows faster than any polynomial in $n$. Similarly, we derive an analogous blowup criterion for a subclass of first-order systems of linear ODEs. Finally, we discuss the implications for the simulation of analog systems governed by ODEs and exemplarily apply our framework to a simple model of neuronal dynamics$-$the leaky integrate-and-fire neuron$-$heavily employed in neuroscience. |
| title | Complexity Theory meets Ordinary Differential Equations |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2604.09790 |