Akitoshi Kawamura. Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete. In Proceedings of the 24th IEEE Conference on Computational Complexity (CCC 2009), Paris, France, July 2009. DOI = 10.1109/CCC.2009.34
ロナルド・ブック賞(学生論文賞)受賞
本文.pdf(平成21年5月1日作成,英文,二段組レター判12頁)
同じ本文を一段組にしたもの.pdf(平成21年5月1日作成,英文,一段組レター判19頁)
発表資料.pdf(英文)
(非公式の邦訳です 正版は英文頁を御覧下さい)
多項式時間可計算かつリプシッツ連続なる函数が与える初期値問題の解が多項式空間完全たり得ることを示す.これは葛(K. Ko)氏による昭和58年(1983,Inform. Contr. 58)の問に答えるものである.証明ではまずリプシッツ条件が系に課する制約が,多項式空間計算における記憶の使い方に或る制限を設けるのに似ていることを指摘する.そしてこの制限がしかし多項式空間完全を奪うには至らないことを,量化命題論理式評価からの帰着により示す.同じ手法によりヴォルテラ積分方程式に関する同氏平成3年(STOC 1991)の二つの予想も決着する.