<p>A first observation in the direction of decidability of ODEs is <a href="http://arxiv.org/pdf/1204.6671v1.pdf">this</a> paper by Avigad, Clarke and Gao, which classifies the complexity of <em>$\delta$-decidability</em>, in which solutions are to be found within a certain bounded error (the "delta") in one direction.</p>

<p>one of the main results is that $\delta$-solvability of (<a href="http://en.wikipedia.org/wiki/Lipschitz_continuity">Lipschitz-continuous</a>) ODEs is $\mathrm{PSPACE}$-complete.</p>

CC BY-SA 3.0
2015-03-22T22:18:35.540Z
Thank you. But what I am looking for is, a system of classifying all differential equations into some specific kind of complexity classes; where _reducing_ problems would mean: A differential equation can be solved, if (and only if) there is another one that can be solved.
sonamtex
CC BY-SA 3.0
2015-03-02T23:40:57.803Z
2015-03-02T23:40:57.803Z
cody
<p>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?</p>

<p>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?</p>

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

<p><a href="https://mathoverflow.net/questions/158068/simple-example-of-why-differential-equations-can-be-np-hard">https://mathoverflow.net/questions/158068/simple-example-of-why-differential-equations-can-be-np-hard</a></p>

<p>This article:</p>

<p><a href="http://www.cs.princeton.edu/~ken/MCS86.pdf" rel="nofollow noreferrer">http://www.cs.princeton.edu/~ken/MCS86.pdf</a></p>

<p>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.</p>

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

CC BY-SA 3.0
2015-03-03T07:22:51.873Z
See [Computational Complexity of Smooth Differential Equations](http://www.lmcs-online.org/ojs/viewarticle.php?id=1247&layout=abstract)
Kaveh
CC BY-SA 3.0
2015-03-03T08:05:58.160Z
And also [Complexity Theory for Operators in Analysis](http://www-imai.is.s.u-tokyo.ac.jp/~kawamura/papers/sopoly/).
Damiano Mazza
CC BY-SA 3.0
2015-03-09T17:52:28.983Z
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.
<cc.complexity-theory><complexity-classes><computability><dynamic-algorithms>
Can differential equations be classed into their own complexity classes?
sonamtex
# Can differential equations be classed into their own complexity classes?

(Asked by: username_0 on 2015-03-02)

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>

This article:

<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.

**Tags:** cc.complexity-theory, complexity-classes, computability, dynamic-algorithms
> **Comments:**
> **username_1**: See [Computational Complexity of Smooth Differential Equations](http://www.lmcs-online.org/ojs/viewarticle.php?id=1247&layout=abstract)  
> **username_2**: And also [Complexity Theory for Operators in Analysis](http://www-imai.is.s.u-tokyo.ac.jp/~kawamura/papers/sopoly/).  
> **username_3**: 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  

---

## 1 answers

### Answer by username_4 on 2015-03-02. Score: 6

A first observation in the direction of decidability of ODEs is [this](http://arxiv.org/pdf/1204.6671v1.pdf) 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](http://en.wikipedia.org/wiki/Lipschitz_continuity)) ODEs is $\mathrm{PSPACE}$-complete.

> **Comments:**
> **username_0**: Thank you. But what I am looking for is, a system of classifying all differential equations into some specific kind of complexity classes; where _reducing_ problems would mean: A differential equation can be solved, if (and only if) there is another one that can be solved.  

---

