連続系計算量理論の深化と展開

科研費26700001 若手研究A 平成26〜29年度

研究目的

計算可能性理論は実数を含む連続世界の問題にも古くから応用されてきたが,これを更に時間・空間的な計算効率(計算量)を考慮して精密化する研究が近年の理論的基盤の整備によって急速に進みつつある.本計画ではこの理論を隣接分野の手法と関連づけて深化するとともに,これまで計算理論で扱われなかった対象の複雑さ解析にも応用する.このような研究は,計算機による数値算法の能力と限界を明らかにし,効率的な精度保証計算を基礎づけるという実際上の意義があるのみならず,従来計算の観点を入れずに記述されてきた数学的諸現象を深く理解することにも繋がる.

リンク

成果

  1. A. Kawamura, F Steinberg and M. Ziegler. Computational complexity theory for classes of integrable functions. Constructivism and Computability, Kanazawa, Japan, March 2015.
  2. 河村. 解析函数の完全精度演算の計算量と実装について. 研究集会「証明論・計算論とその周辺」. 京都府京都市左京区. 平成26年12月25日.
  3. A. Kawamura and H. Ota. Small complexity classes for operators in analysis. In Proc. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS), Budapest, Hungary, August 29, 2014.
  4. A. Kawamura, F. Steinberg and H. Thies. Analytic functions in iRRAM. Presented at the Eleventh International Conference on Computability and Complexity in Analysis (CCA). Darmstadt, Germany, July 23, 2014.

随時更新予定