布尔表达式的最小化是NP完全的吗？
我知道布尔可满足性是 NP 完全的，但它是布尔表达式的最小化/简化，我的意思是采用符号形式的给定表达式并生成符号形式的等效但简化的表达式，NP 完全？ 我不确定是否会从可满足性降低到最小化，但我觉得可能是这样。 有人有确切消息么？
I know that boolean satisfiability is NP-Complete, but is the minimization/simplification of a boolean expression, by which I mean taking a given expression in symbolic form and producing an equivalent but simplified expression in symbolic form, NP-Complete? I'm not sure that there's a reduction from satisfiability to minimization, but I feel like there probably is. Does anyone know for sure?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
好吧，这样看：使用最小化算法，您可以将任何不可满足的表达式压缩为文字
false，对吗？ 这样就有效解决了SAT。 所以至少一个完整的最小化算法必须是NP-hard的。根据 Para Black 的评论，该问题（也称为最小等效 DNF 问题）实际上被证明是非 NP 且Σ2P-complete 作者：克里斯·乌曼斯于 1998 年。
Well, look at it this way: using a minimisation algorithm, you can compact any non-satisfiable expression to the literal
false, right? This effectively solves SAT. So at least a complete minimisation algorithm must be NP-hard.As per the comment by Para Black, the problem (which is also known as the minimum equivalent DNF problem) was actually shown to be non-NP and Σ2P-complete by Chris Umans in 1998.