3-OCC-MAX SAT np-complete？

Question

假设3-OCC-MAX SAT是所有CNF公式的语言，其中每个变量最多出现在3个子句中。这个问题是NP完全的吗？我试图找到SAT和这个问题之间的karp约简，但我找不到它。

Answer 1

这个问题是NP完全的。很容易看出它是在NP中(猜测模型；在多项式时间内检查它)。

第一次尝试(失败)

为了显示NP硬度，我提出了以下结构：

考虑一个有n个变量的3-SAT实例F。考虑一个子句[L1, L2, L3]。定义新的变量p1、p2、p3。定义Li等价于pi。然后，用新的变量替换原来的子句。

这会产生以下形式的子句：

[p1, p2, p3]
[-p1, L1]
[-L1, p1]
[-p2, L2]
[-L2, p2]
[-p3, L3]
[-L3, p3]

对所有子句执行此操作，并始终使用新变量。

请注意，变量p1到p3恰好使用了三次，而L1到L3使用了两次。这个结构是多项式的。

编辑:我目前认为这还不是一个有效的解决方案:原始文字可能会超过最大出现次数3。

第二次尝试

这个想法是对文字的每次出现都使用新的变量。

设M是3SAT公式中变量出现的次数(可以改进)。对于3SAT CNF中的每个原子A，将以下内容添加到得到的3-OCC-MAX SAT公式中：

q0 <- A
q1 <- q0
q2 <- q1
q3 <- q2     
q4 <- q3
...
q_M <- q_M-1
q_M+1 <- q_M
q0 <- q_M+1

对-A的实例执行相同的操作。

p0 <- -A
p1 <- p0
p2 <- p1
p3 <- p2     
p4 <- p3
...
p_M <- p_M-1
p_M+1 <- p_M
p0 <- p_M+1

此外，添加以下内容以确保q行或p行为真。

-p0 <- qM+1
-q0 <- pM+1

现在，添加原始3SAT CNF中的子句，其中文字L的第n次出现被替换为qn。没有“第0次出现”，即我们从1开始计数；因此在此上下文中不使用q0和p0以及qM和pM。注意，A和-A出现了2x，变量p0、q0、p_M+1、q_M+1出现了三次，变量p_i、q_i出现了三次，其中i最多出现在1和M之间三次。