Computational complexity of smooth differential equations

Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick, Martin Ziegler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Citations (Scopus)


The computational complexity of the solution 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 in hope of understanding the intrinsic hardness of solving the equation numerically. 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 ≥ 2, the solution h can be hard for the counting hierarchy if g is of class C k .

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Proceedings
Number of pages12
Publication statusPublished - 2012
Externally publishedYes
Event37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012 - Bratislava, Slovakia
Duration: Aug 27 2012Aug 31 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7464 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Computational complexity of smooth differential equations'. Together they form a unique fingerprint.

Cite this