玉置 卓
【研究分野・テーマ】
一般に最適化問題の最適解を求めることは容易ではありません。主な理由として、組合せ爆発 (NP困難)、データサイズが大きすぎる、データが不完全、などが挙げられます。そのような計算困難な最適化問題に対して
・厳密アルゴリズム (指数時間)
・近似アルゴリズム (多項式時間〜定数時間)
・量子アルゴリズム
といったアプローチで取り組んでいます。具体的な対象としては
・充足可能性問題 (SAT)
・制約充足問題 (CSP)
・局所ハミルトニアン問題 (LH)
などの組合せ最適化問題を扱っています。また、アルゴリズムの設計と解析の研究と対をなす、計算理論の研究も行っています。キーワードは
・近似不可能性
・論理回路複雑性
・量子優位性
などです。
【研究に関連する図表】
