跳至內容

布林可滿足性問題

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

可滿足性(英語:Satisfiability)是用來解決給定的真值方程式,是否存在一組變數賦值,使問題為可滿足。布林可滿足性問題(Boolean satisfiability problemSAT )屬於決定性問題,也是第一個被證明屬於NP完全的問題。此問題在電腦科學上許多的領域皆相當重要,包括電腦科學基礎理論演算法人工智能硬件設計等等。

直觀描述

  • 對於一個確定的邏輯電路,是否存在一種輸入使得輸出為真。

參見

外部連結

SAT Solvers:

Conferences/Publications:

Benchmarks:

SAT solving in general: