7

我知道布尔可满足性是 NP-Complete 的，但它是布尔表达式的最小化/简化，我的意思是采用符号形式的给定表达式并以符号形式产生等效但简化的表达式，NP-Complete？我不确定从可满足性到最小化是否有减少，但我觉得可能有。有人有确切消息么？

4

1 回答 1

8

好吧，这样看：使用最小化算法，您可以将任何不可满足的表达式压缩为文字false，对吗？这有效地解决了SAT。所以至少一个完整的最小化算法必然是NP完全NP难。

于 2009-03-01T16:45:11.563 回答