TY - GEN
T1 - Computational complexity of smooth differential equations
AU - Kawamura, Akitoshi
AU - Ota, Hiroyuki
AU - Rösnick, Carsten
AU - Ziegler, Martin
PY - 2012
Y1 - 2012
N2 - 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 .
AB - 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 .
UR - http://www.scopus.com/inward/record.url?scp=84865013518&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865013518&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-32589-2_51
DO - 10.1007/978-3-642-32589-2_51
M3 - Conference contribution
AN - SCOPUS:84865013518
SN - 9783642325885
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 578
EP - 589
BT - Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Proceedings
T2 - 37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012
Y2 - 27 August 2012 through 31 August 2012
ER -