假设 3-OCC-MAX SAT 是所有 CNF 公式的语言，其中每个变量最多出现在 3 个子句中。这个问题是NP完全的吗？我试图找到 SAT 和这个问题之间的 karp 减少，但我找不到。
问问题
69 次
1 回答
0
这个问题是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 恰好使用了 3 次，而 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-row 或 p-row 为真。
-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 出现 3 次，变量 p_i、q_i，其中 i 在 1 和 M 之间最多出现 3 次。
于 2020-10-16T22:57:05.847 回答