充足可能性問題(SAT問題)は、最も基本的で重要なNP完全問題の1つである。この問題は、和積標準形(CNF)論理式を入力とする。CNF論理式に対して、O(1.239^m)時間アルゴリズムを提案した[SODA1998]。2005年に、そのアルゴリズムをもとにした、O(1.234^m)時間アルゴリズムを提案した[ISAAC2005]。この講演では、ブーリアンネットワーク解析への応用可能性のある、これらのアルゴリズムについて詳細に説明する。「セミナー」に戻るホーム。