问两次-3SAT NP-完全
EN

Stack Overflow用户

提问于 2015-02-17 21:21:00

回答 1查看 213关注 0票数 3

我想解决以下关于3SAT的问题。“两次-3SAT输入:如何证明它是NP-hard的，并且有多个可满足的赋值”

发布于 2015-02-18 18:09:37

从3SAT减少:取一个3SAT实例，并添加一个带有伪子句的伪变量，即[original formula] AND (dummy OR not dummy OR dummy)。不管dummy的值是什么，它都不会影响公式的计算值。

结果实例的令人满意的赋值是原始实例的两倍，因为每个原始赋值都会为修改后的公式生成两个:一个使用dummy = true，另一个使用dummy = false。因此，结果实例至少有2个令人满意的赋值，仅当原始实例至少有一个。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/28562522

复制

相似问题

问两次-3SAT NP-完全EN