本页使用了标题或全文手工转换

布尔可满足性问题

维基百科,自由的百科全书
跳转至: 导航搜索

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

布尔可满足性问题是第一个被证明的NPC问题

直观描述[编辑]

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

外部連結[编辑]

SAT Solvers:

Conferences/Publications:

Benchmarks:

SAT solving in general: