姜咏江 今天得闲，浏览了 ECCC 网站，好像是以色列主办的，过去没接触过。浏览 2017 年的文章，首先被 ScottAaronson 教授的 P ? = NP 一文所吸引。文章太长，总而言之是 P/NP 问题很难，很重要等，没见到问题已经解决的字样。 数学证明具有很强的逻辑性，但基础是概念和事实。文中提到尚未见到多项式时间的算法出现，因而难说 P 与 NP 是否相等。我所做的工作正是找到了 SAT problem 这个 NP-complete 问题的多项式时间算法，因而我想 Scott Aaronson 的文章落后了。 P/NP 问题很多人走的是企图用旧有的概念和方法去证明两者之间的关系，失败的原因就是没有见到一个 NP-complete 问题的多项式时间算法，又不能肯定这种算法是否存在，也就是缺乏事实依据，缺乏应有的概念，故而没法用逻辑来推导出确定正确的结论。 多见证明文章冗长，几乎都成了一本书，早就失去了数学证明的特色，难免出现逻辑或概念上的偏差，也不易被人完全读懂，自然让人们认可起来也相当困难。这大概是 P/NP 问题证明的盲点。 我所追求的是具体的 SAT 问题算法，以子句消去法这个算法去探讨多项式时间复杂度，进而踩在库克的肩膀上，去说明了 P=NP 罢了。 子句消去法可以在多项式时间内求出 SAT 的满足解，前文已经提到。昨天又将《 All Solutions of SAT by Eliminate Clause and Its Possible Solutions Method 》一文放到了 arXiv.org 网站上，编号 1823386 。之前还放上了《 Clause Elimination Method for Vertex Cover 》，编号 1791707 ；《 Solve the Maximum Clique by the New Data Structure 》，编号 1791794 。毫无疑问，运用文中介绍的算法都可以证明在多项式时间将需要的解求出来。 这些论文都以介绍实际算法为主，进而依据算法的实际来证明这几个 NP-complete 问题，都可以针对最坏的情况，在多项式时间获得解答。因为我实实在在地给出了前所未有的算法，因而我有充分的底气，敢说 P=NP 。 Scott Aaronson 教授什么时候能够见到我的子句消去法和以上的论文，或许会惊讶。也许这几篇论文不太 English ，我猜他也会理解我的算法，也会写出新的论题。 事实是概念的基础，正确概念是论证的基石 。 2017-2-18
姜咏江 SAT 的定义中是不允许出现重复子句的，但在子句消去的过程中，会出现降阶的子句块中有重复的子句。 t 阶子句块变量唯一解是因为它有 2 t-1 个相同的表现值（ 1 ≤ t ≤ k ）。在消去子句的过程中很难事前知道那些子句会重复，这样证明消去重复子句这一步算法时间复杂度为多项式时间就很困难。不过我们可以从总体上来探讨。 假如 SAT 子句的最高阶是 k ，那么子句块的总数不会超过 C n k +C n k-1 +...+C n 1 个。如此有 m 个变量表现值相同的子句块（ 1 ≤ m ≤ k-1 ）最多有 C n -m k-m +C n -m k-m-1 +...+C n -m 1 +1 个，那么有 m 个变量表现值相同的子句块的子句总数不会超过 C=2 k-m +2 k-m-1 +...+1 个。 C 是一个有限常数。因此，任何一个剩余的子句块的子句数数，都不会超过这个数。在小于常数 C 个数中，消去重复数的算法时间复杂度无疑是 O(1) 。而剩余子句块最多还是 C n k +C n k-1 +...+C n 1 个，所以 SAT 总体去掉子句块中重复子句的算法时间复杂度是 O( n k ) 。 2016-11-9
子句消去法 k-CNF=1 求满足解的算法如下（原文见附件）： （1） 化简：将变量有唯一表现值设定为解，将相关子句消去； （2） 去掉子句块中重复子句； （3） 判断变量可选解，无可选解转（ 10 ）； （4） 变量有 2 个可选解，记录可选解数量，选择另一变量，转（ 3 ）； （5） 变量有唯一可选解，确定该变量唯一解，消去相关子句； （6） 对剩余子句重复（ 1 ）至（ 5 ），若全部变量设置完成（无剩余子句）转（ 9 ）； （ 7 ） 对剩余全有 2 个可选解变量，从任意一变量设定解出发，依据变量唯一解消去子句； （ 8 ） 有剩余子句且有变量值未设定转（ 7 ）； （ 9 ） 得满足解结束。 （ 10 ） 无解结束。 要证明算法时间复杂度为多项式类型，就应该指出其每一步都是多项式类型时间复杂度。我们分步来解释： 第一步，化简的过程是判断每个变量的全部表现值是否相同。 即使一个一个表现值进行对比，由于 k-CNF 最多有 2 k C n k 个子句，而且表现值只有 0 和 1 ，那么最多需要也就是 2 k C n k 次。可以知道最坏的情况下的时间复杂度为 O( n k ) ，实际上具有相同变量的子句数会远远低于这个数。 我们只要计算一下 0 和 1 的数量，只要有一个计数为零，那么就可以设定另一个值。这时的时间复杂度为 O(1) 。 如果消去子句的过程也考虑，那么最坏也是最好的时间复杂度为 O( n k ) ，此时就没有必要再继续考察变量了，因为所有的子句都可以消去了。 第二步，去掉子句块中重复的子句的工作是在子句块中完成的。 k-CNF 的子句块最多有 2 k 个，无论你如何比较结果都不会超过常数 2 k ！，因而这一步的时间复杂度为 O(1) 。 第三步，判断变量可选解，最多要判断 2 n 次，还可以如下理解。 由于逻辑变量是定义在｛ 0 ， 1 ｝这个集合上的，因而必须对选择的变量分别选择 0 和 1 运用变量唯一解子句消去法检查是否会出现无解剩余子句块或多解剩余子句块。由于子句块最多有 C n k 个，所以需要考察的剩余子句块不会超过 C n k 个。 0 和 1 各进行一次，那么这一步算法时间复杂度也是 O( n k ) 。 第四步，这是简单判断，显然算法时间复杂度为 O(1) 。 第五步，变量确定只有唯一解。 当变量只有一个可选解的时侯，这个可选解就是变量的唯一解。消去含有这个变量这个表现值的所有子句，最多也不超过 2 k C n k 个。因而这一步算法时间复杂度不超过 O( n k ) 。 第六步，这是对（ 1 ）至（ 5 ）的有限次重复。 第七步，如果对可选解考察得到的是每个变量都有 2 个可选解。这时只要对任意一个变量取 0 或 1 的值，消去相关子句，然后再消去剩余降阶子句块中变量唯一解的子句。根据变量可选解的确定过程知道，这一过程中成为唯一解的变量相关子句都会被消去，而剩下的子句中的变量一定还有 2 个可选解。于是可以继续对剩下的子句集再进行这样的操作，直至全部子句消去。变量都有 2 个可选解的子句块最多有 C n k 个。所以这一步最坏的算法时间复杂度也不超过 O( n k ) 。 这一步不好理解的地方是任意设定一个变量的值就能够将关联段的子句全部消去吗？是不是会产生没有解的情况？如果出现没有解，再去重复求解，不就变成了概率求解了吗？ 实际情况是当每个变量都有 2 个可选解到时候，可以按照子句消去法，从变量的任意值出发，都可以求出满足解，不会出现没有解的情况，这是由变量可选解的定义直接相关的。变量的可选解是通过子句消去法剩余各阶有无解定义的，和变量可取值是不同的概念。 第八、第九、第十步都是 O(1) 这样的算法时间复杂度。 总之，依据多项式时间复杂度复杂度的低阶不算的特性，有限次的 O( n k ) 之和的算法时间复杂度仍然是 O( n k ) 的特性，用子句消去法求 k-SAT 满足解的算法时间复杂度为 O( n k ) 。 姜咏江 2016-10-19 附件： 2016子句消去法求k-SAT满足解.pdf
多项式型与指数型算法悖论 姜咏江 在 P/NP 问题的讨论中，很重要的概念就是 O( n k ) 与 O(2 n ) 的时间复杂度问题。其实这是一条悖论！请看： 定理 ：任何有限个多项式相加仍然是一个多项式。 那么， n 个元素集合的非空子集共有 C n 1 + C n 2 + C n 3 +…+ C n n -1 + C n n =2 n -1 个。毫无疑问，等式的左边是多项式型（因为任何一项都是一个多项式），而等式的右边是指数型。 请问，我们求子集过程的算法时间复杂度是 O( n k ) 还是 O(2 n ) ？ 2015-7-22
标签: 多项式时间复杂度
