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

Question

在 3SAT 的情况下，我们将得到 12(3C2*2*2) maybe.and 而不是 2 个含义，当 m 是子句的数量时，这将形成一个 12m 边的图在 3 CNF 中，我们仍然可以在结果图中找到强连通分量。使 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

Answer 1

很遗憾，3-SAT无法在2-SAT中表达，所以不能像2-SAT那样简单

但是，存在许多与搜索 3-SAT 的多项式时间算法相关的工作。这个想法是找到可以使 3-SAT 实例 "Fixed-Parameter Trackable" (FPT).

的标准

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

I understand 2 SAT can be solved in Polynomial time finding out Strongly Connected Components. What about doing the same for 3SAT?