回复网友汪小龙的友情提醒

姜咏江

 [4]汪小龙  2015-7-6 11:22

博主回复(2015-7-5 21:04)：我已在Quartus II上设计电路测试过，解法定理没有问题。
============================================
对于小的算例有效，不能说明对所有的k-SAT都有效。一般的算例都是容易解的，有些k-SAT是特别难解的。有人从理论上证明过，3-SAT在子句与变量数目比值在4-5之间的某个值会发生相变，出现特别难解的算例。找到这些算例本身就很难。在SAT competition网站有很多很难得算例，如果你的算法能极快地攻克他们，去参加SAT competition，就能很快得到国际承认。

关于3-CNF-SAT我将文中的例题到EDA软件Quartus II设计成电路，还对6个变量下全部子句的2-CNF也同时测试了一下。同我在证明文中的结论一样。

图1  不完全3-cnf和完全2-cnf测试

针对网友提出的问题我回答如下：

1.       理论上能够解决的问题，应该对任何算例都适用，不会有特例。

2.       你说的值会发生变化不知是指什么？还要说清楚的问题是n个变量的k-CNF的子句数最多是C_2n^k个。这样子句最多的k-CNF，我们可以称之为完全合取范式。如果k=3，那么3-CNF最多有2n(2n-1)(2n-2)/3!而已，如果某所谓3-CNF的子句多于这个数，那么其中必有重复的子句。这种重复的子句不应该存在。

3.        “有人从理论上证明过，3-SAT在子句与变量数目比值在4-5之间的某个值会发生相变，出现特别难解的算例。”我敢说这个人肯定没有注意到k≤2n，而子句总数不能超过C_2n^k个这样的事情，因而他犯了重复出现子句的错误。

4.       k≤2n，子句数为C_2n^k个的k-CNF的值一定为0。

将这句话做为定理，证起来也十分容易。因为子句为C_2n^k个的k-CNF中若有k个变量或者非的子句，则一定有对应的反子句。例如C_2n³个子句的3-CNF中，有x4’+x7+x9’子句，则必有x4+x7’+x9子句在其中，它们是互反子句。所以无论如何，C_2n³个子句的3-CNF=0。

最后要说的是k-CNF-SAT成立是有条件的，对一个确定的k-CNF来说，n个逻辑变量的某些值是k-CNF-SAT成立的，而也有某些值使之不成立。这一点从图1就可以看到。

透彻的理论研究，不必将所有人的观点都照顾到，也不必一一拜读，只要方法和论证都正确，倒应该让那些似是而非的说法回归到正确的理论论证上来。抱歉，现在我相信国内能够有人理解，不忙用蹩脚的英文讨论。

因为直接回复许多表示做不到，因而另独写文。

2015-7-6