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

lmcs:960 - Logical Methods in Computer Science, February 11, 2014, Volume 10, Issue 1
Computational Complexity of Smooth Differential Equations

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

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


Source : oai:arXiv.org:1311.5414
DOI : 10.2168/LMCS-10(1:6)2014
Volume: Volume 10, Issue 1
Published on: February 11, 2014
Submitted on: June 25, 2015
Keywords: Computer Science - Computational Complexity,Computer Science - Numerical Analysis,Mathematics - Numerical Analysis


Share

Browsing statistics

This page has been seen 35 times.
This article's PDF has been downloaded 7 times.