Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-642-32589-2_51 | Logical Methods in Computer Science |
Keywords | DocType | Volume |
various assumption,function g,polynomial-time computable,class c k,class c,computational complexity,following result,solution h,ordinary differential equation h,intrinsic hardness,smooth differential equation | Journal | 10 |
Issue | ISSN | Citations |
1 | Logical Methods in Computer Science, Volume 10, Issue 1 (February
11, 2014) lmcs:960 | 7 |
PageRank | References | Authors |
0.68 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akitoshi Kawamura | 1 | 102 | 15.84 |
| Hiroyuki Ota | 2 | 7 | 0.68 |
| Carsten Rösnick | 3 | 14 | 1.98 |
| Martin Ziegler | 4 | 62 | 9.21 |