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

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

研究目的

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

リンク

成果

随時更新予定

  1. 廣島佳汰，河村彰星．初等的に追跡される無理数．情報処理学会研究報告2023-AL-192(5)（第192回アルゴリズム研究会）．宮城県仙台市青葉区，令和5年3月．
  2. 萩原普賢．2階ホロノミック列の極限符号．群・環・言語と計算機科学の周辺領域．京都府京都市左京区，令和5年2月．
  3. 河村彰星，萩原普賢．2階ホロノミック列の極限符号．冬のLAシンポジウム．京都府京都市左京区，令和5年2月．
  4. M. Konečný, S. Park and H. Thies. Extracting efficient exact real number computation from proofs in constructive type theory. To appear.
  5. A. Kawamura. Polynomial-time equivalent representations of compact sets in Euclidean spaces. Continuity, Computability, Constructivity (CCC) 2022. Padua, Italy, September 2022.
  6. K. Hiroshima. A number that has an elementary trace function and no elementary sum approximation. Continuity, Computability, Constructivity (CCC) 2022. Padua, Italy, September 2022.
  7. （講義）河村彰星．実函数の計算理論．第19回組合せ最適化セミナー．京都府京都市左京区，令和4年7月．
  8. M. Konečný, S. Park and H. Thies. Certified computation of nondeterministic limits. In Proc. 14th NASA Formal Methods Symposium (NFM) Lecture Notes in Computer Science 13260, 771–789. Pasadena, CA, USA, May 2022.
  9. （招待講演）S. Park. Verified computation over real numbers and other continuous objects. Second Japan-Russia Workshop on Effective Descriptive Set Theory, Computable Analysis and Automata. Akita, Japan, March 2022.
  10. R. Gozzi. Analog characterization of complexity classes. Second Japan-Russia Workshop on Effective Descriptive Set Theory, Computable Analysis and Automata. Akita, Japan, March 2022.
  11. A. Kawamura. Average-case polynomial-time computability of Hamiltonian dynamics. First Japan-Russia Workshop on Effective Descriptive Set Theory, Computable Analysis and Automata. Nomi, Japan, March 2021.
  12. 河村彰星． 時間限定の下での中間次数について． 第7回山陰基礎論・解析学研究集会．鳥取県米子市． 令和2年1月．
  13. 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.
  14. （招待講演）A. Kawamura. Gray code representation and polynomial-time approximability. Computability Theory and Foundations of Mathematics (CTFM) 2019. Wuhan, China, March 2019.
  15. 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.
  16. 河村，レシーヌ．グレー符号と乱択近似可能実数．情報処理学会第172回アルゴリズム研究会．山形県米沢市，平成31年3月．
  17. 河村．グレー符号と乱択近似可能数．数学基礎論若手の会．沖縄県国頭郡恩納村．平成30年11月．
  18. （招待講演）A. Kawamura. Applying ideas in discrete complexity theory to the continuous world. Continuity, Computability, Constructivity (CCC) 2018. Faro, Portugal, September 2018.
  19. A. Kawamura, F. Steinberg and H. Thies. A class for second-order linear-time computability. Continuity, Computability, Constructivity (CCC) 2018. Faro, Portugal, September 2018.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. A. Kawamura, H. Thies and M. Ziegler. Applications of average-case complexity to problems in analysis． 夏のエルエーシンポジウム． 千葉県山武郡九十九里町． 平成30年7月．

河村彰星