Twice-3SAT是NP完全问题

3

我想解决有关3SAT的以下问题。 "TWICE-3SAT输入:如何证明它是NP难的,并且具有多个可满足分配"

1个回答

3
减少3SAT问题:将一个3SAT实例加上一个虚拟变量和一个虚拟子句,即 [原公式] AND (虚拟 OR 非虚拟 OR 虚拟) 。无论虚拟变量的值是什么,它都不会影响公式的计算结果。
结果实例的满足方案数量是原实例的两倍,因为每个原始方案在修改后的公式中生成两个方案:一个是虚拟 = 真,另一个是虚拟 = 假。 因此,如果原始实例至少有一个满足方案,则结果实例至少有2个满足方案。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接