algorithm - 3 SAT算法的复杂度？

Question

我有一个有趣的 3SAT 算法，我想实现它，但无法编写相同的代码，因此无法查看它是否真的有效。该算法在此处的 Microsoft Word 文件中定义： DropBox Link for 3SAT algorithm 我不知道该算法是否真的有效，以及它的复杂性如何。不过，我真的很想知道它的复杂性。请帮我解决这个问题，就好像它是在多项式时间内那样我会证明 P = NP！

Answer 1

正如您的算法所述，

此方法可能需要相当长的时间，因为每次行数可能乘以 2（结果为 2 ^m，其中 m 是子句数）

因此，算法的最坏情况运行时间是指数的，而不是多项式的。您希望在许多情况下，由于输入中的巧合，运行时间会更短，但最坏情况下的运行时间是评估 P 与 NP 问题的方式。

Answer 2

我可以建议您阅读我的论文http://arxiv.org/ftp/arxiv/papers/1411/1411.2901.pdf 在那里您会发现一个常见的拆分机制来确定可满足性，这显然与您的程序相似。该过程在每个步骤中都是多项式的（实际上是线性的），但问题是公式长度在每个步骤中都会增加。（正如您的问题的答案之一所指出的那样）。在本文中，我已经解决了是否以及在何种情况下系统地防止这种爆炸的问题。