布尔可满足性问题

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

直观描述
 对于一个确定的逻辑电路，是否存在一种输入使得输出为真。

参见 
 NP-complete問題列表
 幾乎完備（）問題與弱完備（）問題
 ASR-complete
 Ladner理論
 NP困难
 P/NP问题

外部連結
SAT Solvers:
Chaff 
HyperSAT 
Spear 
The MiniSAT Solver 
UBCSAT

Conferences/Publications:
SAT 2007: Tenth International Conference on Theory and Applications of Satisfiability Testing  
Journal on Satisfiability, Boolean Modeling and Computation
Survey Propagation

Benchmarks:
Forced Satisfiable SAT Benchmarks 
IBM Formal Verification SAT Benchmarks
SATLIB 
Software Verification Benchmarks 

SAT solving in general:
http://www.satlive.org 
http://www.satisfiability.org 
Sat4j 

计算机逻辑
形式方法
NP完全问题