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

Question

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

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

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

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

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

我的问题是:

这个算法的运行时间是多少？这是否证明了与 P=NP 相关的任何事情，因为我认为这个算法非常有效。我以前的算法让别人失望了，所以这次请花时间分析一下算法，因为这是我的辛勤工作。

Answer 1

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

在实践中，当变量分散时(因为它们在典型的扫雷关卡中)，它工作得非常快。

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

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