Computational Complexity of Smooth Differential Equations

2013/11/30 by Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick +1 · 1 citation
Computer Science · Mathematics · #cs.CC #cs.NA #math.NA

paper · pdf · doi:10.2168/lmcs-10(1:6)2014

published as Logical Methods in Computer Science, Volume 10, Issue 1 (February 11, 2014) lmcs:960 · 15 pages, 3 figures

arxiv created 2014/02/08 · arxiv updated 2015/07/01

Abstract

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¹; for each k≥2, the solution h can be hard for the counting hierarchy even if g is of class C^k.

Cited by

• Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides

Related

• Complexity Blowup for Solutions of the Laplace and the Diffusion Equation
• Fast algorithms for differential equations in positive characteristic
• Computational complexity of solving polynomial differential equations over unbounded domains with non-rational coefficients
• On the complexity of solving ordinary differential equations in terms of Puiseux series
• Computational complexity of solving polynomial differential equations over unbounded domains