再请杜立智详细解析姜咏江解决了3SAT难题如何？

科学网上的牛人杜立智还是很有影响力的。一篇博文《详细解析天才的姜咏江解决了3SAT难题》至今已有1017次阅读，20次评论，很好。

我以讨论的心态从事科学研究，目的是能够从批评中得到启发。杜老师的轻蔑带有讽刺意味的解析评论，是激发我前进的动力。所以我感谢杜立智。

还是被杜老师认为是脑残的“子句消去法”，有了独特的感觉，更需要象杜立智这样的功底深厚的人批评。博文地址：http://blog.sciencenet.cn/blog-340399-928224.html  

姜咏江

2015-9-22

附录：杜立智博文和一些评论

详细解析天才的姜咏江解决了3SAT难题

各位，70余岁高龄的姜咏江博主，名校计算机专业退休老教师，一次又一次地声称解决了世界难题。蒙他看得起，多次点名要求我予以评判。

我已经多次评论过，他的那一套荒谬可笑，他还要继续，并还要点名要我评。我就恭敬不如从命了，反正他的天才解决方案，我稍稍一看，立即看懂，所以也不花什么时间精力。

我这里表这个态：看算法的论文关键是必须进入思路，哪怕别人表达不太好，推敲一下很快进入思路就能看懂。对于这个世界任何高档次高难度的算法论文，只要不涉及其他领域专门的知识，主要是复杂的思路和基础数学，我都能很快进入思路很快看懂，并能很快确定算法到底难不难，有多高的价值，作者实力如何。两种语言，中文英文。而不像大量论文和基金评审专家猪，根本看不懂就做评论。

下面是他最近声称解决了3SAT问题的方法，岂止3SAT，4，5，6SAT…等等他都解决了！

一个逻辑多项式如果存在一项的值是1，那么这个逻辑多项式的值一定就是1。同样，一个逻辑项的存在为0的因子，那么这个逻辑项的值一定是0。逻辑变量非的值，一定是逻辑变量值的反码。逻辑运算的这些基本规律是子句消去法计数成立的基础。

 本文用“+”表示或运算，用“’”表示非运算，与运算符号省略。

 我们可以利用逐次消去n个变量或其非运算一方，通过n次消去，最终确定消去的变量取值是否是合取范式值为1 的解。这叫子句消去法。用子句消去法进行改造，获得了下面的子句消去计数法。

用子句消去计数法求解k-CNF-SAT问题算法如下：

（0）      设立n元单侧计数器：x₁’x₂’x₃’…x_n-1’xn’[],x₁’x₂’x₃’…x_n-1’xn [],…, x₁x₂x₃…x_n-1x_n []，共计2ⁿ个。计数器后面的方括号内放k个变量都在其中的子句数。计数器初值为0。

（1）      去掉值总为1的恒一子句，则n元k-CNF的子句最多剩有。

 从前到后检查每个子句，并将k个变量都在某计数器中的计数器加1。这一过程显然是多项式时间。

（2）      计数后，寻找计数器为0的计数器名称，以其每个变量表示的反码取值，得到的n位二进制数就是这个k-CNF-SAT的全部解。

（3）      若没有计数器值为0，则表示此k-CNF-SAT无解。

例1，f(x₁,..., x₆)= (x₁+x₁'+x₂')(x₂+x₃+x₄)(x₁'+x₃'+x₄')(x₁'+x₂+x₅')(x₂+x₃+x₆)(x₁+x₅+x₆')，求满足

f(x₁,..., x₆)=1的解。

（0）设计数器x₁’x₂’x₃’…x₅’x₆’[],x₁’x₂’x₃’…x₅’x₆ [],…, x₁x₂x₃…x₅x₆ []，共计64个。

（1）去掉恒一子句(x₁+x₁'+x₂')，剩(x₂+x₃+x₄)(x₁'+x₃'+x₄')(x₁'+x₂+x₅')(x₂+x₃+x₆)(x₁+x₅+x₆')

（2）剩下非恒一合取范式的第一子句使含x₂x₃x₄标识的计数器都加1；第二子句使含x₁'x₃'x₄'标识的计数器都加1；继续5次，查遍所有子句。

（3）令为0计数器的变量取反码值即得解。例如，计数器x₁’x₂’x₃ x₄’x₅’x₆ [0]，于是得f(x₁,..., x₆)值为1的解有：（110110）。

（4）一次性可以写出所有解。互为反码标识的计数器都为0，则对应逻辑变量组合双方都是解。

验证：

 对于所得解可以带入原式验证。将x₁=1、x₂=1、x₃=0、x₄=1、x₅=1、x₆=0带入原式得：f(1,1,0,1,1,0)=1。

3.           概念与性质

 为什么子句消去计数法就能够求出k-CNF=1的解？它的证明就在下面的概念和方法中。

定义1：如果子句中同时有逻辑变量和其反表示，则称子句为恒一子句。

 显然，恒一子句的值总是1，与逻辑变量的取值无关。

定义2：所有包含变量x的非恒一子句叫x相关子句。

定义3：我们将n对互反变量只取变量或变量非，得到的n个变量组合，叫一侧。显然，n个变量的一侧有2ⁿ个。

 子句消去计数法的计数器就是记录一侧含有的子句数量的。

定理1：n个变量合取范式k-CNF中一侧相关子句数最多为C_n^k。

证明：因为一侧只有n个变量，从中取出k个为C_n^k。

 此定理可以用来检查给定的合取范式是否不正确。如果给出的合取范式的一侧相关子句超过这个数，则可判定合取范式有错误。

定义4：将合取范式一个变量的值定为1的子句消去求解的方法，称为子句消去法。

 显然，子句消去法经过n次消去，若没有剩余子句，则k-CNF是可满足的，反之不满足。

定理2：非恒一子句全体，消去x相关子句中，一定不含有其反变量x’。

证明：因为非恒一子句x与x’是不同时出现在一个子句，所以消去x相关子句，x’相关子句依然存在。

完全定理：n个逻辑变量所成的k元合取范式k-CNF，最多有C_2n^k个子句。非恒一子句最多有个。

证明：因为每个子句的元素可以是逻辑变量或它的非，这相当从2n个元素中取出k个的组合数，即为。而恒一子句最多有个，所以非恒一子句最多有个。

推论：完全合取范式的值恒为0。

 因为完全合取范式包含x与x’的所有相关子句。所以用子句消去法无论经过怎样的n次消去子句，都不能使剩余没有子句。

可满足定理：若非恒一子句中互反变量有一侧相关子句不存在，则k-CNF-SAT可满足。

证明：因为x的相关子句全体包含一侧所有的n个变量或其非，如果一侧不存在，则可确定其相反一侧变量逐一消去，依据定理2可知最终没有剩余子句。

 满足定理是我们进行k-CNF-SAT求解子句消去计数算法正确性的依据。

步数定理：用子句消去计数法确定k-CNF可满足全部解，最多用了C_2n^k次检查。

 因为子句数不超过C_2n^k,得证。

 步数定理告诉我们，上面介绍的求解算法是一个多项式时间算法。

各位，包括计算机专业的专家们，包括计算机专业的一大部分基金评审专家猪，你们是否能立即看懂了？

我断言，大比例这样的人会半天看不懂！

首先一个问题，他的方法对吗？

我告诉你们，他的方法毫无疑问是对的！

那么，姜博主真的是天才了？这么顶级的世界难题他一下子就解决了，甚至仅仅只是“回去想了想”？

姜博主的整个工作，相当于是在解这样一个方程x=x，一样的无聊。

尽管如此，我还是佩服姜老师的智商，一个70余岁的老人，他玩的一些花样，大量计算机专业高职称高学历的垃圾一点头脑的人是看不懂的。

记得有这样一个谜语：七七四十九，和尚庙里有。

他洋洋洒洒这么长的一段所谓“算法和证明”，其实只要一句话就可以概括。我就不概括了。

这就是姜老师解决世界难题的方法。

联想到上一次他声称解决了整数子集和问题，他那个方法和程序若是自己独立完成的，表明他的头脑没有衰退，智商很高。因为我判断大量杂牌一点头脑的计算机专业的人是做不出来的。

部分网友的评论：