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

科研費26700001　若手研究Ａ　平成26～29年度

研究目的

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

リンク

成果

  1. （招待講演）A. Kawamura. Applying ideas in discrete complexity theory to the continuous world. Second Workshop on Mathematical Logic and its Application. Kanazawa, Japan, March 2018.
  2. A. Kawamura, F. Steinberg and M. Ziegler. On the computational complexity of the Dirichlet Problem for Poisson's Equation. Mathematical Structures in Computer Science 27(8):1437–1465, December 2017.
  3. A. Kawamura and F. Steinberg. Polynomial running times for polynomial-time oracle machines. In Proc. Second International Conference on Formal Structures for Computation and Deduction (FSCD), Leibniz International Proceedings in Informatics 84, Paper 23, 18 pages. Oxford, UK, September 2017.
  4. A. Kawamura, H. Thies and M. Ziegler. Average Case Complexity for the N-body problem. Computability in Europe 2017. Turku, Finland, June 2017.
  5. （招待講演）河村彰星．アナログ計算機と計算可能性．第19回全脳アーキテクチャ勉強会．神奈川県川崎市幸区．平成29年5月9日．
  6. （招待講演）河村彰星．解析学における計算量．日本数学会年会特別講演．東京都八王子市．平成29年3月25日．
  7. （招待講演）河村彰星．実数計算の理論と実践――連続世界の計算限界．オペレーションズリサーチ学会数理計画（RAMP）シンポジウム．新潟県新潟市西区，平成28年10月14日．
  8. A. Kawamura, F. Steinberg and H. Thies. Data-types for multidimensional functions in reliable numerics—Implementations inspired by Real Complexity Theory. The 19th Japan-Korea Joint Workshop on Algorithms and Computation (WAAC). Hakodate, Japan, August 2016.
  9. A. Kawamura, F. Steinberg and M. Ziegler. Complexity theory of (functions on) compact metric spaces. In Proc. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 837–846. New York, USA, July 2016.
  10. A. Kawamura, F. Steinberg and M. Ziegler. Towards computational complexity theory on advanced function spaces in analysis. In Proc. Computability in Europe (CiE), Lecture Notes in Computer Science 9709, 142–152. Paris, France, July 2016.
  11. A. Kawamura, N. Müller, C. Rösnick and M. Ziegler. Computational benefit of smoothness: Parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy. Journal of Complexity 31(5):689–714, October 2015.
  12. A. Kawamura. Reducibility in polynomial-time computable analysis. Dagstuhl Seminar, Joint Session of 15391 “Algorithms and Complexity for Continuous Problems” and 15392 “Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis”. Wadern, Germany, September 24, 2015.
  13. A. Kawamura, F. Steinberg and M. Ziegler. Towards computational complexity theory on advanced function spaces in analysis. Continuity, Computability, Constructivity—From Logic to Algorithms (CCC). Kochel am See, Germany, September 17, 2015.
  14. A. Kawamura and M. Ziegler. Invitation to real complexity theory: Algorithmic foundations to reliable numerics with bit-costs. The 18th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC). Incheon, Korea, August 21, 2015.
  15. T. Katayama and A. Kawamura. On the image and length of polynomial-time computable curves. Twelfth International Conference on Computability and Complexity in Analysis (CCA). Tokyo, Japan, July 14, 2015.
  16. A. Kawamura. Computational complexity of real functions. German-Japanese Workshop on Theory and Practice of Real Computation. Tokyo, Japan, July 12, 2015.
  17. （招待講演）A. Kawamura. Weihrauch reducibility in polynomial-time computable analysis. Sixteenth International Workshop on Logic and Computational Complexity (LCC). Kyoto, Japan, July 4, 2015.
  18. A. Kawamura, F. Steinberg and M. Ziegler. Computational complexity theory for classes of integrable functions. Constructivism and Computability, Kanazawa, Japan, March 3, 2015.
  19. （招待講演）河村彰星．連続世界の計算量．情報処理学会第百五十一回アルゴリズム研究会・人工知能学会第九十六回人工知能基本問題研究会（併催）．愛知県名古屋市昭和区，平成27年1月14日．
  20. 河村彰星．解析函数の完全精度演算の計算量と実装について．研究集会「証明論・計算論とその周辺」．京都府京都市左京区，平成26年12月25日．
  21. A. Kawamura and H. Ota. Small complexity classes for computable analysis. In Proc. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science 8635, pp. 432–444. Budapest, Hungary, August 29, 2014.
  22. A. Kawamura, F. Steinberg and H. Thies. Analytic functions in iRRAM. Eleventh International Conference on Computability and Complexity in Analysis (CCA). Darmstadt, Germany, July 23, 2014.

河村彰星