我想到了一种通过以下方法解决3SAT问题的算法：
1）取cnf方程中至少有一个共同变量的所有子句找到所有这些组合并将它们放入名为“intersection”的列表中。“交集”列表现在包含交集子句组。
2）接下来，我们将一组特定的“交集”中的所有子句转换为DNF因为至少会有一个共同的变量，我不认为它会在指数时间。
3）下一步，我们将得到的所有DNF转换为单个DNF，因为它们在原始方程中都用与门隔开。
4）如果得到的DNF中有一个子句，则该方程是可满足的，否则该方程是不可满足的这是因为不相交的子句（没有共同变量的子句）不会影响整个方程，最后，如果我们“和”那些得到的DNF，它只会乘以变量并将变量添加到现有子句（如果有的话）。
我的问题是：
这个算法的运行时间是多少，这证明了与p=np有关的任何东西，因为我认为这个算法是非常有效的。其他人对我以前的算法很失望，所以这次请花点时间分析算法，因为这是我的辛勤工作。
最佳答案
我正是用这个算法来做扫雷器解算器的。
在实践中，当变量分散开来时，它的工作速度非常快（因为它们在典型的扫雷艇级别）。
然而，对于硬3-sat问题，步骤2和步骤3中的扩展到单个dnf最终需要指数时间，因为每次我们组合子句时，潜在项的数量都会随着子句长度的乘积而增加。
所以，总而言之，这对于一些SAT问题是一个非常有用的方法，但是它具有指数最坏情况的性能，所以对于P=NP没有什么可说的。
关于algorithm - 通过简化DNF来解决3SAT问题？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32550421/