# Can differential equations be classed into their own complexity classes?

Problems have been, as a whole, classified, thanks to Computational Complexity. But, in differential equations, is it possible to classify differential equations depending on their computational structure?

For example, if a first order non-homogeneous equation is comparatively difficult to solve than a, say, 100th order homogeneous equation, can they be classified as separate convexity classes, given the method to solve was same? If we vary the process of solving, how random shall the solutions, their existence and stability, and other properties vary?

I would assume that I am partly convinced that solving differential equations might be NP-Hard:

https://mathoverflow.net/questions/158068/simple-example-of-why-differential-equations-can-be-np-hard

http://www.cs.princeton.edu/~ken/MCS86.pdf

has been forcing me ask for the scope of computational complexity according to the solvabality of Differential Equations. Starting with ordinary differential equations, we could classify partial, delay, difference equations etc.

I had once thought of incorporating dynamic programming using the iterates that were calculated while approximating a solution, but lost myself somewhere.

• – Kaveh Mar 3 '15 at 7:22
• – Damiano Mazza Mar 3 '15 at 8:05
• given that (solving) diophantine equations can have a computattional complexity model and the fact that several clases of ODEs (e.g constant coefficent ODEs) can be mapped to diophantine equations, this gives a hint that can be done – Nikos M. Mar 9 '15 at 17:52

A first observation in the direction of decidability of ODEs is this paper by Avigad, Clarke and Gao, which classifies the complexity of $\delta$-decidability, in which solutions are to be found within a certain bounded error (the "delta") in one direction.
one of the main results is that $\delta$-solvability of (Lipschitz-continuous) ODEs is $\mathrm{PSPACE}$-complete.