algorithm - 我知道 2 SAT 可以在多项式时间内解决，找出强连通分量。为 3SAT 做同样的事情怎么样？

Question

如果是 3SAT 而不是一个子句有 2 个含义，我们可能会得到 12(3C2*2*2)在该结果图中找出强连通分量。这个使 3 SAT 成为 P 问题的陈述有什么问题？例如。

(a+b) = (-a->b).(-b->a)
(a+b+c) = (-a->(b+c)).(-(b+c)->a).....4 more like this
        = (-a ->((-b->c).(-c->b)))....2 for each like this

score 0 · Accepted Answer

不幸的是，3-SAT不能用表示2-SAT，所以不能像 2-SAT 那样简单。

然而，存在许多与为 3-SAT 搜索多项式时间算法相关的工作。这个想法是找到可以使 3-SAT 实例“固定参数可跟踪”（FPT）的标准。

我可以向您推荐 Stefan Szeider 的文章On Fixed-Parameter Tractable Parameterizations of SAT，其中有一段关于将 SAT 实例视为图形并在图形中搜索参数以使 SAT 问题可跟踪的文章。

1 回答 1