布尔可满足性问题

可滿足性(英語:Satisfiability)是用來解決給定的真值方程式,是否存在一组变量赋值,使問題为可满足。布尔可滿足性問題(Boolean satisfiability problemSAT )屬於決定性問題,也是第一个被证明屬於NP完全的问题。此問題在電腦科學上許多的領域皆相當重要,包括電腦科學基礎理論演算法人工智慧硬體設計等等。

直观描述

  • 对于一个确定的逻辑电路,是否存在一种输入使得输出为真。

参见

外部連結

SAT Solvers:

Conferences/Publications:

Benchmarks:

SAT solving in general: