論文

査読有り
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

エクスポート
BibTeX RIS