algorithm - 3SAT 通过 DNF 简化解决？

Question

我想到了一种通过以下方法解决 3SAT 问题的算法：

1）取cnf方程中至少有一个共同变量的所有子句。找到所有这些组合并将它们放入名为“Intersection”的列表中。列表“Intersection”现在包含相交子句组。

2）接下来，我们将特定组“Intersection”中的所有子句转换为 DNF。由于至少有一个共同变量，我认为它不会在指数时间内出现。

3）接下来，我们将所有获得的 DNF 转换为单个 DNF，因为它们在原始方程中都用 AND 门分隔。

4) 如果得到的 DNF 中有一个子句，则方程是可满足的，否则方程是不可满足的。这是因为不相交的子句（没有任何共同变量的子句）不会影响整个方程，最后如果我们与获得的 DNF 进行“与”，它只会将变量相乘并添加到现有的条款（如果有的话）。

我的问题是：

该算法的运行时间是多少，这是否证明了与 P=NP 相关的任何事情，因为我认为该算法非常有效。我之前的算法被其他人失望了，所以这次请花点时间分析算法，因为这是我的努力。

Answer 1

我正是使用这个算法来制作扫雷求解器。

在实践中，当变量分散时（就像它们在典型的扫雷级别中一样），它的工作速度非常快。

然而，对于一个困难的 3-SAT 问题，将步骤 2 和 3 扩展到单个 DNF 最终会花费指数时间，因为每次我们组合子句时，潜在术语的数量都会随着子句长度的乘积而增加。

因此，总而言之，对于某些 SAT 问题，这是一种非常有用的方法，但具有指数级的最坏情况性能，因此对于 P=NP 无话可说。