最小化布尔表达式NP-Complete？

Question

我知道布尔可满足性是NP-Complete，但它是布尔表达式的最小化/简化，我的意思是以符号形式给出一个给定的表达式，并以符号形式生成一个等价但简化的表达式，NP-Complete？我不确定从可满足性到最小化的减少，但我觉得可能存在。有人知道吗？

Answer 1

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