組み合わせ問題に関する複雑さの調査およびそれらのアルゴリズムに関する研究
理論計算機科学はアルゴリズム理論を中心としたコンピュータサイエンスの1分野です。コンピュータ自身が研究対象であり、「コンピュータって何ができるんだろう？そして、コンピュータにできないことってどんなことなんだろう？」という素朴な疑問を追及する学問分野と言えます。本研究室では、特に計算量理論とその応用に関する研究を中心に行っています。
主な研究成果
(1) H. Tohyama and M. Tomisawa, Complexity of Police Officer Patrol problem, JIP, 30, 307-314 (2022)
【概要】警察官パトロール問題と呼ぶ新しいアークルーティング問題を提案し，同問題の計算量がNP完全であることを示した．
(2) 加賀谷，冨澤，遠山，k Generalized Lunar Lockout Variant問題の計算の複雑さ, 電子情報通信学会論文誌D, Vol. J105-D, No.3, pp. 144-153 (2021)
【概要】PSPACE完全であることが示されているGeneralized Lunar Lockout Variantと呼ばれるスライディングブロックパズル問題の複雑さに関する研究．電子情報通信学会論文誌 D：情報・システム 学生論文特集号において学生論文特集秀逸論文を受賞．
(3) H. Tohyama, E. Kamei and M. Watanabe, Operator valued inequalities based on Young’s inequality, Advances in Operator Theory, Volume 8, article number 29 (2023)
【概要】Youngの不等式の改良の１つであるAlzerらの不等式に基づき，新しい作用素不等式を構築した．2024年度AIOT最優秀論文賞を受賞．
どのような産学官連携ができるか
スケジューリング問題など，現実社会に現れる様々な最適化問題に対する解法の提案とその開発
SDGs該当番号
