Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete
Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete
复制标题
Lipschitz 连续常微分方程是多项式空间完备的
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Kawamura
中科院分区：
文献类型：
--
作者：
A. Kawamura
翻译后摘要。在回答高的问题在1983年提出的，我们表明，一个初始值问题的多项式时间可计算的，Lipschitz连续函数可以有一个多项式空间的完全解决方案。关键的见解很简单：Lipschitz条件意味着微分方程中的反馈很弱。我们定义了一类具有同样弱反馈的多项式空间计算表，并证明了它们仍然是多项式空间完备的。同样的技术也解决了柯的两个问题后，沃尔泰拉积分方程。
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.