連続系の複雑さを解明する計算理論

科研費18H03203 基盤研究B 平成30~令和4年度

研究目的

離散的な計算問題にあっては、現実的な計算モデルに基づく計算困難さの同定と、その困難さを回避・克服するアルゴリズム設計とが、互いに補い合う両輪となって研究が深まっている。これに比べると連続系のアルゴリズム(解析学・数値計算)では、計算困難さの理論的な枠組(第二型計算理論)の基礎は整ってきたものの、従来は一般的で粗略な解析しかできず不十分な面がある。本計画では、離散的な領域で既に役立っている、パラメタ計算量や平均時解析などのやや高度な解析手法を、理論的に自然な形で連続系計算に拡張する。またそれを、現実的に意味をもつ数理科学・物理の諸分野の微分方程式・計算幾何・離散力学系などの諸問題の複雑度の理解に繫げることを目指す。

リンク

成果

随時更新予定

  1. A. Kawamura, F. Steinberg and H. Thies. Second-order linear-time computability with applications to computable analysis. In Proc. 15th Annual Conference on Theory and Applications of Models of Computation (TAMC), Lecture Notes in Computer Science 11436, 337–358. Kitakyushu, Japan, April 2019.
  2. (招待講演)A. Kawamura. Gray code representation and polynomial-time approximability. Computability Theory and Foundations of Mathematics (CTFM) 2019. Wuhan, China, March 2019.
  3. A. Kawamura and U. Léchine. On randomized polynomial-time approximability of real numbers and sets. Third Workshop on Mathematical Logic and its Applications (MLA). Nancy, France, March 2019.
  4. 河村,レシーヌ.グレー符号と乱択近似可能実数.情報処理学会第172回アルゴリズム研究会.山形県米沢市,平成31年3月.
  5. 河村.グレー符号と乱択近似可能数.数学基礎論若手の会.沖縄県国頭郡恩納村.平成30年11月.
  6. (招待講演)A. Kawamura. Applying ideas in discrete complexity theory to the continuous world. Continuity, Computability, Constructivity (CCC) 2018. Faro, Portugal, September 2018.
  7. A. Kawamura, F. Steinberg and H. Thies. A class for second-order linear-time computability. Continuity, Computability, Constructivity (CCC) 2018. Faro, Portugal, September 2018.
  8. H. Hamamoto, A. Kawamura and M. Ziegler. On proving parameterized polynomial time computability of compositions of fundamental functions. Workshop on Computability Theory and Foundations of Mathematics (CTFM) 2018. Tokyo, Japan, September 2018.
  9. A. Kawamura, F. Steinberg and H. Thies. Computable analysis and computability in linear time. Workshop on Computability Theory and Foundations of Mathematics (CTFM) 2018. Tokyo, Japan, September 2018.
  10. A. Kawamura. Average-case polynomial-time computability of the three-body problem. Dagstuhl Seminar 18361: Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis, Wadern, Germany, September 2018.
  11. A. Kawamura, H. Thies and M. Ziegler. Average-case polynomial-time computability of Hamiltonian dynamics. In Proc. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), Leibniz International Proceedings in Informatics 117, Article 30. Liverpool, UK, August 2018.
  12. A. Kawamura, F. Steinberg and H. Thies. Parameterized complexity for uniform operators on multidimensional analytic functions and ODE solving. In Proc. 25th Workshop on Logic, Language, Information and Computation (WoLLIC), Lecture Notes in Computer Science 10944, 223–236. Bogotá, Colombia, July 2018.
  13. A. Kawamura, H. Thies and M. Ziegler. Applications of average-case complexity to problems in analysis. 夏のエルエーシンポジウム. 千葉県山武郡九十九里町. 平成30年7月.