证明双重SAT是NP完整的

Question

众所周知的SAT问题已定义 这里 为了参考。

双向问题定义为

美元

我们如何证明它是NP完整的？

将不止一种证明的方式将不胜感激。

Answer 1

这是一个解决方案：

显然，double-sat属于$ { sf np} $，因为ntm可以按以下方式确定double-sat：在布尔值输入公式$ phi（x_1， ldots，x_n）$上两者都满足$ phi $。

为了证明Double-Sat是$ { sf np} $ - 完整，我们将SAT减少到Double-Sat，如下：

在输入$ phi（x_1， ldots，x_n）$：

1. 引入一个新的变量$ y $。
2. 输出公式$ phi'（x_1， ldots，x_n，y）= phi（x_1， ldots，x_n） wedge（y vee bar y）$。

如果$ phi（x_1， ldots，x_n）$属于SAT，则$ phi $至少具有1个满足分配，因此$ phi'（x_1， ldots，x_n，y）$至少具有2个通过分配$ y = 1 $或$ y = 0 $的新变量$ y $，因此满足新的条款（$ y vee bar y $），因此满足新条款（$ y vee bar y $） $，...，$ x_n $，$ y $）$ in $ double-sat。

另一方面，如果$ phi（x_1， ldots，x_n） notin text {sat} $，则明显$ phi'（x_1， ldots，x_n，x_n，y）= phi（x_1，x_1， ldots ，x_n） wedge（y vee bar y）$也没有令人满意的分配，因此$ phi'（x_1， ldots，x_n，y） notin notin text {double-sat} $。

因此，$ text {sat} leq_p text {double-sat} $，因此double-sat是$ { sf np} $ - 完整。

Answer 2

您知道$ mathsf {sat} $是np complete。您能找到从$ Mathsf {SAT} $减少到$ Mathsf {double text { - } sat} $吗？也就是说，您能否操纵令人满意的公式，以便结果至少具有两个令人满意的作业？请注意，相同的操作无法使人难以满足。

对于任何公式$ varphi $，公式$ varphi lor f（ varphi）$至少具有两倍的满意屁股数量为$ varphi $，$ f $ a $ f $ a同构具有将所有变量更加命名为新名称。