主題
Search

可滿足性問題


判定給定的以合取正規化表示的布林公式是否存在使其為“真”的賦值。1971年,庫克證明了這個問題是 NP-完全的。


另請參閱

布林代數, 可滿足的

使用 探索

參考文獻

Cook, S. A. 和 Mitchell, D. G. “尋找可滿足性問題的困難例項:一項調查。”在 可滿足性問題:理論與應用 (Piscataway, NJ, 1996) (Ed. D. Du, J. Gu, 和 P. M. Pardalos)。Providence, RI: Amer. Math. Soc., pp. 1-17, 1997。

在 中被引用

可滿足性問題

引用為

Weisstein, Eric W. “可滿足性問題。” 來自 —— 資源。 https://mathworld.tw/SatisfiabilityProblem.html

主題分類