2015年
SAT問題と他の制約問題との相互発展
コンピュータ ソフトウェア
- ,
- 巻
- 32
- 号
- 1
- 開始ページ
- 1_103
- 終了ページ
- 1_119
- 記述言語
- 日本語
- 掲載種別
- 出版者・発行元
- Japan Society for Software Science and Technology
SAT問題は,命題論理式の充足可能性問題,すなわち命題変数を含む論理式に対し,その論理式を真にするような命題変数への値の割り当てが存在するかを決定する問題である.SATは古典的なNP完全問題であり,計算量的には難しい問題であるものの,近年のアルゴリズムの改良とハードウェアの進化によって著しい高性能化が実現された結果として,様々な分野への応用が行われている.本稿ではSATにまつわる研究で現在活発な領域として,関連する問題クラスへの応用やそれにまつわる研究分野との間の交流について,調査し,紹介する.
- リンク情報
-
- CiNii Articles
- http://ci.nii.ac.jp/naid/130004892312
- ID情報
-
- ISSN : 0289-6540
- CiNii Articles ID : 130004892312
- identifiers.cinii_nr_id : 9000283468482