10
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – sonamtex Mar 22 '15 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.