問題の難しさの評価と計算量クラスの階層性の証明に関する研究

keywords.jpg計算量クラス,チューリング機械,オートマトン,並列計算機モデル,システム評価 

岩本 宙造 

CHUUZOU IWAMOTO

division.jpg工学研究院 情報部門

position.jpg教授

研究概要

研究内容

計算時間やメモリ量を多く使えば使うほど,より難しい問題が解けるようになると考えることは自然である。しかし,こういった問題の難しさの「階層性」を理論的に証明することは非常に難しいことが知られている。計算機科学分野で有名な未解決課題である「P≠NP問題」は,その代表例である。
 これまでに当研究室では,直列計算機の基本モデルであるチューリング機械や,並列計算機モデルであるPRAM, 論理回路を用いて,問題の難しさに関するさまざまな階層定理を証明してきた。また,交代性と呼ばれる並列計算手法で,計算がどれだけ高速化できるのかについても理論的に解明してきた。

実用化に向けて(想定業界・用途、課題、企業への期待など)

この分野に関心のある企業等への知見の提供が可能です。
応用分野
組合せ問題や大規模計算を要する研究開発分野

本研究の特徴・優位性

企業などの研究開発における問題について,その難しさに関する知見を提供することが可能です。

detailsubtitle3.jpg

Chuzo Iwamoto, Naoki Hatayama, Yoshiaki Nakashiba, Kenichi Morita, and Katsunobu Imai, 'Translational Lemmas for DLOGTIME-uniform Circuits, Alternating TMs, and PRAMs', Acta Informatica, Vol. 44, No. 5 (2007) pp. 345-359

お問い合わせ