主题
Search

可满足性问题


判定给定的以合取范式表示的布尔公式是否存在使其为“真”的赋值。1971年,库克证明了这个问题是 NP-完全的。


另请参阅

布尔代数, 可满足的

使用 Wolfram|Alpha 探索

参考文献

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。

在 Wolfram|Alpha 中被引用

可满足性问题

引用为

Weisstein, Eric W. “可满足性问题。” 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/SatisfiabilityProblem.html

主题分类