如何证明在多项式时间内可求解的3SAT的约束版本无法发生一次以上的文字发生？

Question

我正在尝试制定作业（从书中摘录 算法 - S. Dasgupta，Ch papadimitriou和UV Vazirani, ，第8章，问题8.6a），我正在阐述它所述的内容：

鉴于3SAT即使仅限于每个字面形式出现两次的公式，也表明，如果每个文字最多出现一次，那么在多项式时间内就可以解决问题。

我试图通过将条款分为多组来解决这个问题：

1. 条款与其余子句没有任何共同的变量
2. 条款仅有1个共同的变量
3. 子句具有2个共同的变量
4. 所有3个变量共有的子句

我的理由是尝试的，认为此类群体的＃是有限的（由于对没有直接存在的限制了不止一次的限制），我们可以尝试首先满足最受限制的组（第4组），然后替换导致较小的限制组（3、2，然后是1），但我意识到这并没有使我无处最多两次，已被证明是NP完整的。

我尝试在线搜索任何提示/解决方案，但我能得到的只是 这个链接, ，其中所述的提示对我来说没有足够的意义，我在这里逐字复制：

提示：由于每个文字最多出现一次，因此将此问题转换为2SAT问题 - 因此，如果字面$ x_i $出现在子句$ c_j $中，并且补充$ x_i $（即$ overline {x_i} $）在条款$ c_k $中，构造一个新的子句$ c_j lor overline {c_k} $。

$ c_j $和$ c_k $每个都有三个文字 - 我没有得到如何通过执行$ c_j lor overline {c_k} $将其转换为2SAT（或$ overline {c_j lor c_k}） $如果我不正确地阅读它）。

在解释提示或提供我可以探索的道路方面的任何帮助都将不胜感激。

Answer 1

如果不丧失一般性，我们可以假设每个变量正好出现一次正面和一次负面的否定性（如果变量仅出现一次设置其值以满足子句并删除子句）。我们还可以假设，变量不会在子句中多次出现（如果变量在子句中呈阳性和负面显示，则满足该子句并可以删除）。这些不会改变满意度。

现在使用 决议规则 为了一一消除变量（因为每个变量完全出现一次，而一旦负面地出现，这是一个确定性的过程）。如果在任何时候我们获得了空条款，则一组条款是不满意的，否则可满足。这是因为：

• 分辨率是一个完整的命题证明系统（即，如果条款在逻辑上是逻辑上暗示的，则仅使用“分辨率规则”从一组条款中衍生），

• 如果逻辑上意味着空子句，则一组子句不满意。

由于每个变量都可以精确解析一次，因此该算法将需要多项式时间。特别是，解决方案的每种应用都会将条款总数减少一个，因此条款的数量不会增加。例如，将分辨率应用于$（x lor b） land（ edimelline {x} lor c） land dots dots）$产量$（b lor c） land dots $，它具有少量子句比决议之前。相反，如果您将其应用于3SAT公式而没有对每个文字的外观数量限制，则应用分辨率可能会导致条款数量呈指数增加。