polynomial-math - 带有两个子句的 SAT 是多项式

Question

具有 k 个一元子句且只有两个子句的 SAT 实例的复杂性是多少？

我想找一篇有这个结果的论文。我找到了一篇问题有点不同的论文。所有变量最多出现两次...

Answer 1

如果我理解正确，这似乎是条款总长度的线性时间。

一元从句立即强制部分变量赋值 τ。如果两个子句中的任何一个在 τ 下不可满足（空），或者某些单元子句冲突，则该实例是不可满足的。否则，仅当两个子句在 τ 下是单位且互补的，即 x̅ 和 x 时，该实例才不可满足。

Answer 2

你的问题有一个complexity in O(n)where n is the total size of clauses。

你有K个一元子句，这些K个一元子句可以被认为是变量的子赋值。如果您不尊重这些一元条款，那么您肯定找不到解决方案（如果存在）。

让我们举个例子来看看你的问题，目标是找到variables.

 variables = _ _ _ _ _ _ _ _
 problem   = 
              x1                 AND
              x4                 AND
              x7                 AND
             -x8                 AND
             -x5                 AND
              x2                 AND
              x3 OR  -x4 OR x5   AND
              x6 OR  -x1 OR x8

 with K = 5.

因为一元子句会将它们的值传播到variables中，所以这个问题与 基本相同：

 variables = x1 x2 _ x4 -x5 _ x7 -x8
 problem   = 
              x3 OR  -x4 OR  x5  AND
              x6 OR  -x1 OR  x8
 with K = 0.

（为了得到这个，我们做了一个线性时间操作）。

并且因为，我们已经知道 x4、x5、x1 和 x8 的值，所以这个问题与：

 variables = x1 x2 _ x4 -x5 _ x7 -x8
 problem   = 
              x3 AND
              x6
 with K = 0.

（为了获得这个，我们再次进行了线性时间操作）。

通过调用与第一个操作相同的函数，我们将获得：

 variables = x1 x2 x3 x4 -x5 x6 x7 -x8
 problem   = 
              true.
 with K = 0.

（我们再次进行了线性时间运算来得出这个结论）。

这给了你最终的解决方案：variables = x1 x2 x3 x4 -x5 x6 x7 -x8 正如你所看到的，找到解决方案只能通过使用线性时间操作来完成。