3 SAT算法的复杂度？
3 SAT algorithm's complexity?
我有一个有趣的 3SAT 算法，我想实现它，但无法为其编写代码，因此无法查看它是否真的有效。
该算法在此处的 Microsoft Word 文件中定义：
DropBox Link for 3SAT algorithm
我不知道这个算法是否真的有效，如果它有效，它的复杂性是什么。不过，我真的很想知道它的复杂性。请帮我把它看成是多项式时间那么我就可以证明 P=NP!
正如您的算法说明所述，
this method may take considerable amount of time as every time the number of rows might get multiplied by 2 (This comes out to be 2m where m is number of clauses)
因此算法的最坏情况 运行 时间是指数级的，
不是多项式。您希望在许多情况下 运行 时间是
由于输入中的巧合而更短，但最坏情况 运行 时间
P vs NP问题是如何评估的。
我可以建议你阅读我的论文http://arxiv.org/ftp/arxiv/papers/1411/1411.2901.pdf
在那里你会发现一个常见的分裂机制来确定可满足性，这显然与你的程序相似。该过程在每个步骤中都是多项式的（实际上是线性的），但问题是公式长度在每个步骤中都会膨胀。 （正如您问题的答案之一所指出的那样）。在论文中，我已经解决了是否以及在什么情况下可以系统地防止这种爆炸的问题。
我有一个有趣的 3SAT 算法，我想实现它，但无法为其编写代码，因此无法查看它是否真的有效。 该算法在此处的 Microsoft Word 文件中定义： DropBox Link for 3SAT algorithm 我不知道这个算法是否真的有效，如果它有效，它的复杂性是什么。不过，我真的很想知道它的复杂性。请帮我把它看成是多项式时间那么我就可以证明 P=NP!
正如您的算法说明所述，
this method may take considerable amount of time as every time the number of rows might get multiplied by 2 (This comes out to be 2m where m is number of clauses)
因此算法的最坏情况 运行 时间是指数级的， 不是多项式。您希望在许多情况下 运行 时间是 由于输入中的巧合而更短，但最坏情况 运行 时间 P vs NP问题是如何评估的。
我可以建议你阅读我的论文http://arxiv.org/ftp/arxiv/papers/1411/1411.2901.pdf 在那里你会发现一个常见的分裂机制来确定可满足性，这显然与你的程序相似。该过程在每个步骤中都是多项式的（实际上是线性的），但问题是公式长度在每个步骤中都会膨胀。 （正如您问题的答案之一所指出的那样）。在论文中，我已经解决了是否以及在什么情况下可以系统地防止这种爆炸的问题。