The computational complexity of the solutions $h$ to the ordinary
differential equation $h(0)=0$, $h'(t) = g(t, h(t))$ under various assumptions
on the function $g$ has been investigated. Kawamura showed in 2010 that the
solution $h$ can be PSPACE-hard even if $g$ is assumed to be Lipschitz
continuous and polynomial-time computable. We place further requirements on the
smoothness of $g$ and obtain the following results: the solution $h$ can still
be PSPACE-hard if $g$ is assumed to be of class $C^1$; for each $k\ge2$, the
solution $h$ can be hard for the counting hierarchy even if $g$ is of class
$C^k$.
Svetlana Selivanova, Lecture notes in computer science, Computational Complexity of Classical Solutions of Partial Differential Equations, pp. 299-312, 2022, 10.1007/978-3-031-08740-0_25.
Ivan Koswara;Gleb Pogudin;Svetlana Selivanova;Martin Ziegler, Lecture notes in computer science, Bit-Complexity of Solving Systems of Linear Evolutionary Partial Differential Equations, pp. 223-241, 2021, 10.1007/978-3-030-79416-3_13.
Ivan Koswara;Svetlana Selivanova;Martin Ziegler, Lecture notes in computer science, Computational Complexity of Real Powering and Improved Solving Linear Differential Equations, pp. 215-227, 2019, 10.1007/978-3-030-19955-5_19.
AKITOSHI KAWAMURA;FLORIAN STEINBERG;MARTIN ZIEGLER, 2016, On the computational complexity of the Dirichlet Problem for Poisson's Equation, Mathematical Structures in Computer Science, 27, 8, pp. 1437-1465, 10.1017/s096012951600013x.
Akitoshi Kawamura;Florian Steinberg;Martin Ziegler, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, Complexity Theory of (Functions on) Compact Metric Spaces, 4646, pp. 837-846, 2016, New York NY USA, 10.1145/2933575.2935311.
Franz Brauße;Margarita Korovina;Norbert Th. Müller, Lecture notes in computer science, Towards Using Exact Real Arithmetic for Initial Value Problems, pp. 61-74, 2016, 10.1007/978-3-319-41579-6_6.
Klaus Weihrauch, 2016, Computability on measurable functions, Computability, 6, 1, pp. 79-104, 10.3233/com-160058.
Matthias Schröder;Florian Steinberg;Martin Ziegler, Lecture notes in computer science, Average-Case Bit-Complexity Theory of Real Functions, pp. 505-519, 2016, 10.1007/978-3-319-32859-1_43.
Stuart M. Harwood;Joseph K. Scott;Paul I. Barton, 2015, Bounds on reachable sets using ordinary differential equations with linear programs embedded, IMA Journal of Mathematical Control and Information, 33, 2, pp. 519-541, 10.1093/imamci/dnu054.