具有 3 个不同变量的 Monotone 3-SAT 是否难以处理？

Question

我给出了以下 SAT 变化：

给定 CNF 中的公式 F，其中每个子句 C 恰好有 3 个不同的文字，并且对于 F 中的每个 C，所有文字都是正数，或者所有文字都是负数。例子：

$F= (x_1\vee x_2 \vee x_4) \wedge ( eg x_2\vee eg x_3 \vee eg x_4) \wedge (x_3\vee x_4 \vee x_5)$

SAT 的这种变体容易处理吗？

到目前为止我的发现：

我怀疑这个问题是 NP 完全问题，因此难以处理。因此，我想执行从 3-SAT 到上述变体的聚合还原。

任意 3-SAT 公式可以转换为单调 3-SAT。

举个例子：

$C_1=(x_1\vee x_2 \vee eg x_3)$ 并定义 $z_3$ 经过 $ eg x_3 \leftrightarrow z_3$ 和 $x_3 \leftrightarrow eg z_3$ 这相当于 $(x_3\vee z_3)\楔形( eg x_3 \vee eg z_3)$.

由此我们得到单调形式 $C_1$ 经过

$(x_1\vee x_2 \vee eg x_3) \leftrightarrow (x_1\vee x_2 \vee z_3)\楔形 (x_3\vee z_3)\楔形( eg x_3 \vee eg z_3)$

通过将这种转换应用于所有子句，我得到了一个同样可满足的单调 3-SAT 公式。

我的缩减为每个非单调子句生成了额外的 2 个子句，其中有 2 个文字，但是如何仅获得具有 3 个不同文字的单调子句？

Answer 1

我现在将尝试回答我自己的问题，并且很高兴收到有关正确性的一些反馈。

就像凯尔琼斯在上面讨论和指出的问题一样，我们可以将任意 3-SAT 公式简化为单调 3-SAT 公式。

例如一个子句 $C=(x_1\vee x_2 \vee eg x_3)$ 可以转换为 $C'(x_1\vee x_2 \vee z_3)\楔形(z_3\vee x_3)\楔形( eg z_3 \vee eg x_3)$. 。可以检查是否 $C$ 是可以满足的 $C'$ 也是可满足的，如果 $C$ 不能满足 $C'$ 也不能满足。

下一步是将所有少于 3 个文字的子句转换为恰好具有 3 个不同文字的子句。

因此以 $C_1=(x_1 \vee x_2)$ 并将其转换为 $C_1'=(x_1 \vee x_2 \vee y_1)\楔形 (x_1 \vee x_2 \vee y_2) \楔形 (x_1 \vee x_2 \vee y_3) \楔形 ( eg y_1 \vee eg y_2 \vee eg y_3)$ 然后再一次如果 $C_1$ 是可以满足的 $C_1'$ 也是可满足的，如果 $C_1$ 不能满足 $C_1'$ 也不能满足。对于负面情况也可以做同样的事情，即 $C_2=( eg x_1 \vee eg x_2)$ 可以转化为 $C_2'=( eg x_1 \vee eg x_2 \vee eg u_1)\wedge ( eg x_1 \vee eg x_2 \vee eg u_2) \wedge ( eg x_1 \vee eg x_2 \vee \负 u_3) \楔形 ( u_1 \vee u_2 \vee u_3)$

通过应用这两种转换，我们可以将任意 3-SAT 实例转换为具有 3 个不同文字的单调 3-SAT 实例。从上面可以很容易看出，变换具有多项式复杂度。因此，由于 3-SAT 是 NP 困难的，因此归约也必须是 NP 困难的。