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

Question

在 3SAT 的情况下，我们可能会得到 12(3C2*2*2) 而不是一个子句的 2 个含义。当 m 是 3 CNF 中的子句数时，这将形成一个 12m 边的图我们仍然可以在结果图中找出强连通分量。使 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 实例“固定参数可跟踪”(FPT) 的标准。

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

您可以在此处找到有关 FPT 的更多信息:https://en.wikipedia.org/wiki/Parameterized_complexity