メンバー

TOP > メンバー > 河村 彰星

河村 彰星

名前 河村 彰星 (Kawamura, Akitoshi)

准教授

E-Mail kawamura (emailアドレスには@kurims.kyoto-u.ac.jp をつけてください)


研究内容 計算論

紹 介

 コンピュータによる計算であれ人間の数学的推論であれ, 情報処理は有限的な操作からなる手順(アルゴリズム)として表されます。 このような知的処理によって何ができて何ができないか探るのが計算理論です。 次のように,有用な計算法を設計することと, その限界を調べることの両面から研究が行われています。

アルゴリズム工学 計算機を様々な大規模問題の解決に役立てるには, その問題のもつ構造や,アルゴリズムの設計によく使われる手法を理解し, うまく利用する必要があります。 計算幾何,資源配分,スケジューリングなど様々な領域の問題について, 数理工学的手法を用いて性能・効率のよいアルゴリズムを設計・分析する研究を行っています。
限界の解明(計算量理論) 個々の問題の解法だけでなく,一般に様々な条件下で何がどこまで計算できるかという限界を探ることも, 情報学の重要な目標です。 計算機構の制約,時間・空間や知識の量,論理的・記述的な複雑さといった各要素が, 情報処理能力にどう関与し,相互にどう関わり合うかを調べることで, 考えている問題に内在する困難さを理解したり, 知的処理の本質的限界に迫ることを目指します。

 私は特に,これらの理論を広い数学的対象に適用することに関心を持っています。 計算理論で最初に対象とされたのは主に離散的・組合せ的な問題ですが, 実数など連続的な対象や高階の計算も, 何らかの形で表されたデータに情報処理を施す問題である以上, その処理・操作の内容に着目して計算論的複雑さを調べることができます(帰納的解析学)。 この分野で計算可能性だけでなく多項式時間を初めとする計算量制限を論ずるための 理論的枠組の整備[6,7]や具体的問題への応用[2,3,8]を行ってきました。
 また並行して,計算幾何を中心とする諸分野の最適化に関する研究もしています[1,4,5]。

  1. A.Kawamura, S.Moriyama, Y.Otachi and J.Pach. A lower bound on opaque sets. Computational Geometry, 80, 13--22, 2019.
  2. 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, 2018.
  3. 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, 2017.
  4. Y.Asao, E. D.Demaine, M. L.Demaine, H.Hosaka, A.Kawamura, T.Tachi and K.Takahashi. Folding and punching paper. Journal of Information Processing 25, 590--600, 2017.
  5. T.Hayashi, A.Kawamura, Y.Otachi, H.Shinohara and K.Yamazaki. Thin strip graphs. Discrete Applied Mathematics 216 (1), 203--210, 2017.
  6. 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, 2016.
  7. A.Kawamura and S.Cook. Complexity theory for operators in analysis. ACM Transactions on Computation Theory 4 (2), Article 5, 2012.
  8. A.Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete. Computational Complexity 19(2), 305--332, 2010.

← BACK TO THE TOP

← BACK TO THE TOP

  • Follow on

Research Institute for Mathematical Sciences (RIMS)