開学40周年記念事業

文字サイズ
検索

学部・大学院

ホーム > 学部・大学院 > 教員紹介 > 情報・知能工学系 > 木村 慧(きむら けい)

木村 慧(きむら けい)

所属 情報・知能工学系
兼務
職名 助教
専門分野 離散最適化 / アルゴリズム
学位 博士(情報理工学)(東京大学)
所属学会 日本オペレーションズ・リサーチ学会 / 電子情報通信学会
E-mail kimura@cs
※アドレスの末尾に「.tut.ac.jp」を補完してください
研究室web http://www.algo.cs.tut.ac.jp/

研究紹介

制約充足問題とは与えられた制約を満たす,有限個の値をとる離散的な変数への値の割当てを求める問題である.この問題は工学に現れる多くの問題を含むことが知られており,様々な分野で研究がなされている.例えば,充足可能性問題やグラフ彩色問題,整数線形不等式系の実行可能性判定といった,人工知能や理論計算幾何学などの分野における基本的かつ重要な問題を含んでいる.このように重要な問題であるため,制約充足問題を解くためのアルゴリズムに関する研究は古くから行われており,現在もなお盛んに研究が行われている.一方で,制約充足問題は一般にはNP困難であり,そのため,この問題をすべての入力に対して効率的に解くアルゴリズムを開発することは難しいと考えられている.そこで,効率的に解ける部分クラスを明らかにする研究が数多く行われているが,(PがNPと異なるという仮定の下で)効率的に解けるための必要十分条件は未だに得られていない.本研究の目的は,この必要十分条件を明らかにし,多項式時間可解性を導くような制約への制限に対する統一的な見解を与えることである.

ページトップへ