3

我想解决以下关于 3SAT 的问题。“TWICE-3SAT 输入：如何证明它是 NP-hard 并且有多个可满足的作业”

4

1 回答 1

2

从 3SAT 减少：取一个 3SAT 实例并添加一个带有虚拟子句的虚拟变量，即[original formula] AND (dummy OR not dummy OR dummy). 无论 dummy 的值是多少，dummy 都不会影响公式的评估值。

结果实例的满意赋值是原始实例的两倍，因为每个原始赋值都会为修改后的公式生成两个：一个 with dummy = true，另一个 with dummy = false。因此，如果原始实例至少有一个，则结果实例至少有 2 个令人满意的分配。

于 2015-02-18T10:09:36.530 回答