Name
Abstract | ||
|---|---|---|
. In answer to Ko’s question raised in 1983, we show that an initial value problem given by a polynomial-time computable, Lipschitz
continuous function can have a polynomial-space complete solution. The key insight is simple: the Lipschitz condition means
that the feedback in the differential equation is weak. We define a class of polynomial-space computation tableaux with equally
weak feedback, and show that they are still polynomial-space complete. The same technique also settles Ko’s two later questions
on Volterra integral equations. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00037-010-0286-0 | Computational Complexity |
Keywords | Field | DocType |
lipschitz condition,initial value problem,lipschitz continuity,ordinary differential equation,volterra integral equation,polynomial time,differential equation,computational complexity | Differential equation,Discrete mathematics,Ordinary differential equation,Integral equation,Lipschitz domain,Lipschitz continuity,Initial value problem,Mathematics,Volterra integral equation,Computable analysis | Conference |
Volume | Issue | ISSN |
19 | 2 | 1420-8954 |
Citations | PageRank | References |
13 | 0.96 | 25 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akitoshi Kawamura | 1 | 102 | 15.84 |