
VOLUME 10, ISSUE 1, PAPER 6
Computational Complexity of Smooth Differential Equations

©Akitoshi Kawamura, University of Tokyo ©Hiroyuki Ota, University of Tokyo ©Carsten Rösnick, Technische Universität Darmstadt ©Martin Ziegler, Technische Universität Darmstadt 
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 PSPACEhard even if g is assumed to be
Lipschitz continuous and polynomialtime computable. We place further
requirements on the smoothness of g and obtain the following
results: the solution h can still be PSPACEhard
if g is assumed to be of class C^{1}; for each k
≥2, the solution h can be hard for the counting
hierarchy even if g is of class C^{k}.

Publication date: February 11, 2014
Full Text: PDF  PostScript DOI: 10.2168/LMCS10(1:6)2014
Hit Counts: 5248 
Creative Commons  