为k-SAT问题解决一周年欢呼

    在科学网上发表子句消去计数法一周年了(http://blog.sciencenet.cn/blog-340399-905817.html)。这应该值得我庆祝。同时我要在此感谢名博主杜立智对该文精彩绝伦的评价(http://blog.sciencenet.cn/blog-327757-905854.html)。

    子句消去计数法（现在我把它称为子句标志消去法）是多项式时间复杂度的算法吗？毫无疑问，是！时至今天我能这么肯定，是因为用这个算法很容易得到k-SAT的全部解！什么是对问题最好的证明？那就是实际解决了问题。

    子句消去计数法求k-SAT的解实在太简单了，以至于杜立智给了最高规格的评价：证明了x=x。至今还无人有证明x=x的方法，我做到了吗？

    我视杜立智为友，是因为他是一个唯一敢肯定这一算法正确性的人，其批评又促进我百思得解。

    如何求得k-SAT的全部解？我这里给出一个3-SAT的例子，只要读者将右面的n位数中含有左面子句的数码且位置相同数同子句一起逐一消去（n位数没有时，只消去子句）。当所有子句消去之后，剩下的n位数的反码都是解！这里n=5，有底纹的部分表示消去了。

    可以将得到的那些n位数（左面下面的3个5位二进制数）带入k-SAT进行验证，可知完全正确。

表1  3-SAT和解标志

     子句最多有2的k次方乘以n取k的组合数，即为2^kC^k_n。子句标志消去法的规模是子句的数量m，在用子句标志消去法求解的过程中根本就没有出现对m的循环，因而m的变化过程是逐次取1到2^kC^k_n这些整数。也就是说该算法时间复杂度为O( m)。需要说明，右面的n位二进制数是装在每一个熟悉二进制表数人的心中的，正如我们熟悉十进制数的数码在什么位置一样。莫把右面的2ⁿ个数看成算法操作的一部分，它们是算法的对象。这正如同x是2ⁿ以内的正整数一样，我们需要将其全部值写出来吗？况且这种子句标志查找的过程可以制造出象加法器一样的运算器，给出相应的机器指令，不会增加算法的时间复杂度。

     希望大家掌握这个求k-SAT所有解的方法，使我能为相关计算作点贡献。更欢迎数学，计算机方面专家给出评价和批评。

姜咏江

 2016-6-27