我想解决以下有关 3SAT 的问题。
“TWICE-3SAT 输入:如何证明它是 NP-hard 并且有多个可满足的作业”
最佳答案
从 3SAT 减少:采用 3SAT 实例并添加一个带有虚拟子句的虚拟变量，即 [original formula] AND (dummy OR not dummy OR dummy) 。无论虚拟人的值是多少，虚拟人都不会影响公式的评估值。
结果实例的令人满意的赋值是原始实例的两倍，因为每个原始赋值为修改后的公式生成两个:一个带有 dummy = true ，另一个带有 dummy = false 。因此，如果原始实例至少有一个，则结果实例至少有 2 个令人满意的分配。
关于algorithm - Twice-3SAT NP-完全，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28562522/