Akitoshi Kawamura ; Hiroyuki Ota ; Carsten Rösnick ; Martin Ziegler - Computational Complexity of Smooth Differential Equations

lmcs:960 - Logical Methods in Computer Science, February 11, 2014, Volume 10, Issue 1 - https://doi.org/10.2168/LMCS-10(1:6)2014
Computational Complexity of Smooth Differential EquationsArticle

Authors: Akitoshi Kawamura ; Hiroyuki Ota ; Carsten Rösnick ; Martin Ziegler

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


    Volume: Volume 10, Issue 1
    Published on: February 11, 2014
    Imported on: January 1, 2013
    Keywords: Computer Science - Computational Complexity,Computer Science - Numerical Analysis,Mathematics - Numerical Analysis

    11 Documents citing this article

    Consultation statistics

    This page has been seen 1197 times.
    This article's PDF has been downloaded 352 times.