首页    期刊浏览 2024年11月08日 星期五
登录注册

文章基本信息

  • 标题:SAT問題と他の制約問題との相互発展
  • 本地全文:下载
  • 作者:酒井 政裕 ; 今井 健男
  • 期刊名称:コンピュータ ソフトウェア
  • 印刷版ISSN:0289-6540
  • 出版年度:2015
  • 卷号:32
  • 期号:1
  • 页码:1_103-1_119
  • DOI:10.11309/jssst.32.1_103
  • 出版社:Japan Society for Software Science and Technology
  • 摘要:

    SAT問題は,命題論理式の充足可能性問題,すなわち命題変数を含む論理式に対し,その論理式を真にするような命題変数への値の割り当てが存在するかを決定する問題である.SATは古典的なNP完全問題であり,計算量的には難しい問題であるものの,近年のアルゴリズムの改良とハードウェアの進化によって著しい高性能化が実現された結果として,様々な分野への応用が行われている.本稿ではSATにまつわる研究で現在活発な領域として,関連する問題クラスへの応用やそれにまつわる研究分野との間の交流について,調査し,紹介する.

国家哲学社会科学文献中心版权所有