English

リプシッツ条件と微分方程式の計算量

Akitoshi Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete. Computational Complexity 19(2), 305–332, May 2010. DOI = 10.1007/s00037-010-0286-0

Akitoshi Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete. In Proceedings of the 24th IEEE Conference on Computational Complexity (CCC 2009), pages 149–160, Paris, France, July 2009. ロナルド・ブック賞(学生論文賞)受賞.DOI = 10.1109/CCC.2009.34

概要

多項式時間可計算かつリプシッツ連続なる函数が与える初期値問題の解が多項式空間完全たり得ることを示す.これは葛(K. Ko)氏による1983年(Inform. Contr. 58)の問に答えるものである.証明ではまずリプシッツ条件が系に課する制約が,多項式空間計算における記憶の使い方に或る制限を設けるのに似ていることを指摘する.そしてこの制限がしかし多項式空間完全を奪うには至らないことを,量化命題論理式評価からの帰着により示す.同じ手法によりヴォルテラ積分方程式に関する同氏1991年(STOC)の二つの予想も決着する.

語句
可計算解析,計算複雑,指数空間,数値計算,常微分方程式,初期値問題,積分方程式,多項式空間,ピカール・リンデレーフの定理,リプシッツ連続