ゲノム情報科学研究教育機構  アブストラクト
Date March 23, 2010
Speaker Dr. 山本真基 (東海大学理学部情報数理学科)
Title 充足可能性問題(SAT問題)を解く O(1.234^m)時間厳密アルゴリズム
Abstract 充足可能性問題(SAT問題)は、最も基本的で重要なNP完全問題の1つである。この問題は、和積標準形(CNF)論理式を入力とする。(節の大きさには制限がない)
1998年、Hirschが、節数 m のCNF論理式に対して、O(1.239^m)時間アルゴリズムを提案した[SODA1998]。そして2005年に、そのアルゴリズムをもとにした、O(1.234^m)時間アルゴリズムを提案した[ISAAC2005]。
この講演では、ブーリアンネットワーク解析への応用可能性のある、これらのアルゴリズムについて詳細に説明する。
「セミナー」に戻る      
 ホーム