Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915991451074560 |
|---|---|
| author | Bournez, Olivier Núñez, Alonso |
| author_facet | Bournez, Olivier Núñez, Alonso |
| contents | When a computer algebra system fails to solve an Ordinary Differential Equation, is this a limitation of its implementation, or a genuine computational barrier?
Three traditions bear on the question. Modern computer algebra algorithms can be extremely efficient: Newton-type methods solve polynomial ODEs over $\mathbb{Q}[[X]]$ in quasi-linear time. Analog models of computation has shown that polynomial ODEs and Turing machines are two presentations of the same phenomenon, with solution length acting as time and precision as space. Computable analysis shows that ODEs can be intrinsically hard -- undecidable, even $\mathsf{PSPACE}$-complete, over compact domains. Comparing these traditions is natural and necessary, yet such comparisons routinely reduce to comparisons of encodings rather than of underlying algorithmic content.
We argue that reverse mathematics provides a representation-invariant lens in which algorithmic content is compared directly. We prove that every level of the Big Five hierarchy is inhabited by a natural statement from classical ODE theory, as an exact equivalence: the regularity of $f$ is an intrinsic algorithmic invariant placing the initial value problem $y'(t)=f(t,y(t))$, $y(t_0)=y_0$, into one of several computational strata, ranging from polynomial-time solvability to transfinite computation.
The resulting stratification acts as a practical diagnostic common to the three traditions. By abstracting from representation, it separates fundamental barriers from the technical shortcomings of symbolic solvers, the artefacts of analog encodings, and the effectivity constraints of computable analysis, identifying the intrinsic parameters (length bounds, radii of convergence, moduli of continuity) under which feasibility is restored. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07128 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides Bournez, Olivier Núñez, Alonso Symbolic Computation Computational Complexity Logic When a computer algebra system fails to solve an Ordinary Differential Equation, is this a limitation of its implementation, or a genuine computational barrier? Three traditions bear on the question. Modern computer algebra algorithms can be extremely efficient: Newton-type methods solve polynomial ODEs over $\mathbb{Q}[[X]]$ in quasi-linear time. Analog models of computation has shown that polynomial ODEs and Turing machines are two presentations of the same phenomenon, with solution length acting as time and precision as space. Computable analysis shows that ODEs can be intrinsically hard -- undecidable, even $\mathsf{PSPACE}$-complete, over compact domains. Comparing these traditions is natural and necessary, yet such comparisons routinely reduce to comparisons of encodings rather than of underlying algorithmic content. We argue that reverse mathematics provides a representation-invariant lens in which algorithmic content is compared directly. We prove that every level of the Big Five hierarchy is inhabited by a natural statement from classical ODE theory, as an exact equivalence: the regularity of $f$ is an intrinsic algorithmic invariant placing the initial value problem $y'(t)=f(t,y(t))$, $y(t_0)=y_0$, into one of several computational strata, ranging from polynomial-time solvability to transfinite computation. The resulting stratification acts as a practical diagnostic common to the three traditions. By abstracting from representation, it separates fundamental barriers from the technical shortcomings of symbolic solvers, the artefacts of analog encodings, and the effectivity constraints of computable analysis, identifying the intrinsic parameters (length bounds, radii of convergence, moduli of continuity) under which feasibility is restored. |
| title | Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides |
| topic | Symbolic Computation Computational Complexity Logic |
| url | https://arxiv.org/abs/2605.07128 |