some image logo

HOME

SEARCH

CURRENT ISSUE

REGULAR ISSUES

   Volume 1 (2005)

   Volume 2 (2006)

   Volume 3 (2007)

   Volume 4 (2008)

   Volume 5 (2009)

   Volume 6 (2010)

   Volume 7 (2011)

   Volume 8 (2012)

   Volume 9 (2013)

   Volume 10 (2014)

      Issue 1

      Issue 2

      Issue 3

      Issue 4

   Volume 11 (2015)

   Volume 12 (2016)

   Volume 13 (2017)

SPECIAL ISSUES

SURVEY ARTICLES

AUTHORS

ABOUT

SERVICE

LOGIN

FAQ

SUPPORT

CONTACT

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

Publication date: February 11, 2014

Full Text: PDF | PostScript
DOI: 10.2168/LMCS-10(1:6)2014

Hit Counts: 5032

Creative Commons