Are there known results on computational complexity of initial value problems of ODEs? As my question may be somewhat vague, I want to mention that I'm mainly interested for results on the computational complexity of one-step methods (Runge-Kutta).

Edit: I forgot to mention that I'am aware of the obvious time complexity results based on the number of function evaluations and the rate of convergence. I'm also aware of the PSPACE-completeness of the solution when the right-side of the equation $y'(t)=f(y(t),t))$ is polynomial-time computable and satisfies the weak Lipschitz condition w.r.t. $y(t)$ (which can be safely assumed in my case). All I want to know is what kind of conditions should an IVP obey to for its solution, $y(t)$, to be computable in polynomial time, if such conditions have beed found.

  • $\begingroup$ I found my answers in a paper by Kawamura (link) at last. $\endgroup$ – Kapoios Feb 6 '15 at 15:44

Your Answer

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

Browse other questions tagged or ask your own question.