库克定义下的 k-CNF-SAT ＝ P 证明（中文版） 姜咏江 Email:accsys@126.com 摘要 ：采用子句消去法证明了斯提芬 . 库克定义下的 NP C 问题 k-CNF-SAT 可以是一个 P 类问题。给出了子句消去法的算法。同时也给出了可以在有限步骤内求出 k-CNF-SAT 问题的解或指出其不满足的条件。 关键词 ： NPC ， P/NP 问题，子句消去法 1. 背景 P/NP 问题曾于 2000 年被美国克雷数学所定为最难的难题，有甚者说其挑战了人类智慧。 2010 年 8 月 6 日， HP LAB 的 Vinay Deolalikar 教授宣布证明了 P!=NP ，证明文章 已经发送到该问题各相关领域专家手中，等待检验，在他的主页上，证明过程已经公布（ PDF 格式共 103 页）。 本文将给出 NP C 问题 k-CNF-SAT 可以是一个 P 类问题的算法和相关证明，跟 Vinay Deolalikar 教授唱个反调，主张 P=NP ，是否会得到学术界认可，有待每个感兴趣的人检验。 2. 子句消 去法求解的算法 一个逻辑多项式如果存在一项的值是 1 ，那么这个逻辑多项式的值一定就是 1 。同样，一个逻辑项的存在为 0 的因子，那么这个逻辑项的值一定是 0 。逻辑变量非的值，一定是逻辑变量值的反码。逻辑运算的这些基本规律是子句消去法成立的基础。 本文用“ + ”表示或运算，用“ ’ ”表示非运算，与运算符号省略。 对于 k-CNF-SAT 问题用子句消去法求解的算法如下： （1） 在合取范式中取第一个子句的一个变量表示（选择过的变量 x ，不选 x’ ，或选过 x’ 则 x 不选），若是变量本身，定其值为 1 ，若是变量非表示，设定变量的值为 0 。 （2） 消去所有含有选择变量表达形式的子句，得到剩余子句。 （3） 若还有剩余子句且有变量未选择，则转到（ 1 ）对剩余合取范式继续执行操作。 （4） 若所有变量皆选过，尚有剩余子句，则表示这不是合取范式此值为 1 的解；不然将前面取值按照变量顺序排好，未取值的变量表示值可以任意（用“ * ”代替）。 例1 ， f ( x 1 , x 2 , x 3 )= ( x 1 '+ x 2 )( x 2 ’+ x 3 ’)( x 2 + x 3 ) ( x 2 ’+ x 3 ) ( x 2 + x 1 ) 。 （ 1 ）由 x 1 ' 令 x 1 =0 ，消去含有 x 1 ' 子句，剩 ( x 2 ’+ x 3 ’)( x 2 + x 3 ) ( x 2 ’+ x 3 ) ( x 2 + x 1 ) ； （ 2 ）由 x 2 ' 令 x 2 =0 ，消去含有 x 2 ' 子句，剩 ( x 2 + x 3 ) ( x 2 + x 1 ) ； （ 3 ）由 x 3 令 x 3 =1 ，消去含有 x 3 子句，剩 ( x 2 + x 1 ) 。 由于此剩余子句的值为 0 ，故 f (0,0,1)=0 。 例2 ， f ( x 1 ,..., x 6 )= ( x 1 + x 1 '+ x 2 ')( x 2 + x 3 + x 4 )( x 1 '+ x 3 '+ x 4 ')( x 1 '+ x 2 + x 5 ')( x 2 + x 3 + x 6 )( x 1 + x 5 + x 6 ') ，求满足 f ( x 1 ,..., x 6 )=1 的解。 （ 1 ）令 x 1 =1 ，剩 ( x 2 + x 3 + x 4 )( x 1 '+ x 3 '+ x 4 ')( x 1 '+ x 2 + x 5 ')( x 2 + x 3 + x 6 ) （ 2 ）令 x 2 =1 ，剩 ( x 1 '+ x 3 '+ x 4 ') （ 3 ）令 x 3 =0 ，则消去值为 1 子句后，无有剩余子句。 于是得 f ( x 1 ,..., x 6 ) 值为 1 的解有：（ ***011 ），其中 * 表示为 0 或 1 不限。 验证 ： 对于所得解可以带入原式验证。将 x 1 =1 、 x 2 =1 、 x 3 =0 带入原式得： f (1,1,0, x 4 ,..., x 6 )=1 。 3. 概念与性质 定义 1 ： n 个逻辑变量全部可取 k 元子句组成的合取范式叫完全合取范式。 定义 2 ：元素对应取反的两个子句称为互反子句。 例如 3-CNF 中有子句 x 2 ’+ x 5 ’+ x 9 和 x 2 + x 5 + x 9 ’ ，它们的表示相反，因而是互反子句。 定义 3 ：如果子句中同时有逻辑变量和其反表示，则称子句为恒一子句。 显然，恒一子句的值总是 1 ，与逻辑变量的取值无关。 性质1 ：合取范式去掉恒一子句，所得合取范式与原合取范式值满足性相同。 完全定理 ： n 个逻辑变量所成的 k 元合取范式 k-CNF ，最多有C 2n k 个子句。 证明 ：因为每个子句的元素可以是逻辑变量或它的非，这相当从 2n 个元素取出 k 个的组合数，即为 C 2n k 。 推论1 ：完全合取范式去除恒一子句，都是互反子句 。 证明 ：根据完全合取范式的定义，去掉恒一子句后，如果某子句的互反子句不在其中，则知这不是完全合取范式。则知必都有互反子句 。 可满足定理 ：子句消去法最终无剩余子句，则此合取范式是可满足的。 证明 ：因为子句消去的条件是值为 1 ，若最终子句全消去，则知原合取范式是可满足的。 步数定理 ：用子句消去法确定了 k-CNF 可满足，最多用了 n 次化简。 此定理从子句消去法定义立得。 4. 3-CNF-SAT 子句数 3-CNF 的恒 1 子句共有： n × 2(n-1)=2n(n-1) 完全 3-CNF 全部子句数： 2n(2n-1)(2n-2)/6=2n(n-1)(2n-1)/3 完全 3-CNF 去掉恒一子句的可能子句数： 2n(n-1)(2n-1)/3-2n(n-1)=2n(n-1) (2n-4)/3 5. 结论 一般 P/NP 问题的描述与斯提芬 . 库克的 NP 、 NPC 定义有不同之处。本文仅是站在伟大的库克的肩膀上，找出了特出 k-CNF-SAT 问题不满足的条件，并推出子句消去法求 k-CNF-SAT 问题满足解的一种方法。 斯提芬 . 库克一脉学术观点认为：若任意 NPC 问题可证明是 P 问题，那么 P=NP 成立。本文给出了 k-CNF-SAT 问题的 n 次化简求解法，并且对于 n 位二进制数是否是 n 元逻辑变量的 k-CNF-SAT 解的验证，也肯定了是典型所谓的“多项式时间”，故可以得出在 斯提芬 . 库克定义的条件下，可以有 NPC ＝ P ，这个结论否定了 P ！ =NP 。 2015-7-4
来自维基百科的NPC问题收集,大多数问题来自： Garey and Johnson's seminal book Computers and Intractability: A Guide to the Theory of NP-Completeness List of NP-complete problem s
关于NP/NPC/NPH的文章转于此处，供以后参考： Part I from http://www.nocoo.us/2009/01/npc-and-nph/ Nocoo.Weblog Professional, Passion and Patient 引言 上图：艺术陈列馆问题（Art Gellery Problem），是一个NP-Complete问题。这里显示了一种解，四个摄像头覆盖了整个艺术陈列馆的每个角落。 P和NP就不讲了，Assert(不明白P和NP的读者不会到达这里看到这一段话)。 P是否等于NP的问题目前仍有争论，我对算法理解不深，暂时没有自己的看法。具体的讨论可以参见： WikiPedia的P=NP?讨论 。不过做点猜想的话，我觉得，从数学美的角度来看，我觉得P=NP。当然，从理性思考角度来看，就像你觉得有没有外星人这个问题一样，理性思考的人会毫不犹豫地给出当然有的答案，P不应该等于NP。 当然大部分计算机科学家认为PNP。 If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in creative leaps, no fundamental gap between solving a problem and recognizing the solution once its found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss Scott Aaronson, MIT 这段话给出的启示还是很令人震惊的：任何懂得欣赏交响乐的人都可以成为莫扎特一样的音乐神童，任何懂得步步演绎问题的人都可以成为高斯一样的数学天才，因为P=NP，则说明解决问题和理解、认识和描述问题本身没有本质区别。 谈点自己的看法：Google的出现其实为我们提出了一种佐证，当你把一个问题描述清楚的时候，基本也就解决了。当你真正遇到一个问题，只要想清楚应该用什么关键字去搜索，问题的答案正在Google上等着你。 The main argument in favour of PNP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. The resolution of Fermats Last Theorem also shows that very simply questions may be settled only by very deep theories. Moshe Y. Vardi, Rice University 最简单的问题却要通过最复杂的理论来解决。 Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required. Anil Nerode, Cornell University 避免偏见，应当总是向两个方向努力。 NP-Complete问题 Cook在1971年给出并证明了有一类问题具有以下性质： 这类问题中任何一个问题至今未找到多项式时间算法； 如果这类问题中的一个问题存在有多项式时间算法，那么这类问题都有多项式时间算法（就是多项式时间内，这类问题可互相规约）。 这类问题中的每个问题称为NP完全（NP-Complete，NPC）。 NP-Hard问题 如果判定问题A满足ANP且NP中的任何一个问题都可在多项式时间内 规约为A ，则称A为NP完全（NP-Complete，NPC）。若NP中的任何一个问题都可以在多项式时间 规约为 判定 问题A ，则称A为NP难（NP-Hard，NPH）。 显然 NPCNPH 。 NP完全和NP难问题的区别是NP难问题无需判断A是否属于NP。验证一个问题A是否为NPC的关键有两点： 一是NP中任何一个问题是否可在多项式时间内规约为A； 其次，是否存在一个字符串，其规模为实例规模的多项式函数，以及是否存在一个多项式时间的验证算法。 由于NPC里包含很多著名的组合最优化问题，经过几代数学家的努力，迄今没有找到多项式时间算法，人们猜想NPC中的任何一个问题 没有 多项式时间算法，即PNPC=。 这里有个图可以帮助你理解这几种问题的相互关系。可以看到，如果P=NP，数学上是比较美的。 一种实践方法 当然上面讲的都是理论。实践当中没有这么复杂，当你遇到一个问题，想判断这个问题是否是NPC时，只需要找一个类似的已知的NPC问题，然后想一个这两个问题之间的多项式时间转换方法即可。 这里有一个列表，包含 已知的著名NP-Complete问题的列表 。重要的NPC问题现在已知3000+。 Part II from http://blog.csdn.net/daijingbo1987/archive/2010/07/30/5775743.aspx P/NP/NP-Complete/NP-Hard 收藏 Part III from http://blog.csdn.net/daijingbo1987/archive/2010/07/30/5775748.aspx NP-hard和NP-complete的区别 对 NP -Hard 问题和 NP-Complete 问题的一个直观的理解就是指那些很难（很可能是不可能）找到多项式时间算法的问题。 因此一般初学算法的人都会问这样一个问题： NP-Hard 和 NP-Complete 有什么不同？根据定义，如果所有 NP 问题都可以多项式归约到问题 A ，那么问题 A 就是 NP -Hard ；如果问题 A 既是 NP-Hard 又是 NP ，那么它就是 NP-Complete 。 NP-Hard 问题类包含了 NP- Complete 。 NP-Complete is a subset of NP.( Note: NP-Complete = NP-HardNP ??) Halting problem 是 NP-Hard 而不是 NP-Complete 。 P 問題：可以用 polynomial 演算法解決的問題，亦即解決時間為 polynomial 時間。 NP 問題：可以用 non-deterministic polynomial 演算法解決的問題。請注意， P 問題既然可以用 polynomial 演算法解決，當然也可以用 non-deterministic polynomial 演算法解決 , 因此所有的 P 問題都是 NP 問題。 NP-HARD ：一個 NP 問題經由 polynomial 演算法轉化之後所成的問題。此處的轉化，一般稱為 reduce 。 NP-COMPLETE ：一個 NP 問題經由 polynomial 演算法轉化之後，仍為 NP 問題。換句話說，所謂的 NP-COMPLETE 問題，就是既為 NP-HARD ，亦為 NP 。也就是說，若只經由 polynomial 演算法來 reduce ，不論如何都在 NP 的範圍內。 NP-HARD 與 NP-COMPLETE 的不同，在於 NP-HARD 不一定屬於 NP 問題。 NP-HARD 可以是 NP 問題，也可以是一個超越 NP 難度的問題 .... 但若是 NP-HARD 的難度仍然是 NP ，則這個 NP-HARD 就是一個 NP-COMPLETE 。 先稍微說明一下 polynomial time reduction 的概念好了 , 假設有 A,B 兩個問題 , 如果我們有一個演算法可以解決 B 問題 , 那麼我們可以利用此演算法在 polynomial time 內也解決 A 問題 , 則我們就說 A 可以 reduce 到 B, 也就是說假如 B 解決了 , A 也可以很容易的解決 ..( 可以想成是 B 比 A 難 ) 但正確的說是： A reduce to B 應該是說我們可以設計一個 Poly-time 的 Algorithm 將 A 的問題轉成 B 問題的型式 , For example, 所有 satisfiability problem 都可以 reduce 到 3-SAT problem. 如 : (x1 V x2) = (x1 V x2 V y1), (x1 V x2 V -y1) -x3 = (-x3 V y1 V y3), (-x3 V -y1 V y3), (-x3 V y1 V -y3), (-x3 -y1 V -y3) (x1 V -X2 V X3 V x4) = (x1 V -x2 V y1), (x3 V x4 V -y1) 故 , 如果我們可以在 P time 裡解 3-SAT 則也可以用此方法解 satisfiability problem. 也就是說如果我們不可以在 P-time 裡解 SAT problem 則也無法在 p-time 解 3-SAT problem 如果一個問題屬於 NP-hard, 那麼所有屬於 NP 的問題都要能 reduce 到這個問題上面 , 也就是說這個問題比所有 NP 的問題都要更難 . 如果一個問題是 NP-complete, 兩個條件 :(1) 此問題屬於 NP (2) 此問題為 NP-hard 也就是說 , NP 的問題裡面 , 有一部份是最難的 , 所有其他的 NP 問題都能 reduce 到這些問題上面這一群問題就稱為 NP-complete 的問題 ! 所以 NP-hard 和 NP-complete 都是比所有 NP 問題都還要難的問題 , 差別在於 NP-complete 還是在 NP 之內 , 是 NP-hard 裡面屬於 NP 的問題 ! 1 ，计算复杂性 这是描述一种算法需要多少 时间 的度量。（也有空间复杂性，但因为它们能相互转换，所以通常我们就说时间复杂性。对于大小为 n 的输入，我们用含 n 的简化式子来表达。（所谓简化式子，就是忽略系数、常数，仅保留最 大 的那部分） 比如找出 n 个数中最大的一个，很简单，就是把第一个数和第二个比，其中大的那个再和第三个比，依次类推，总共要比 n-1 次，我们记作 O(n) ( 对于 n 可以是很大很大的情况下， -1 可以忽略不计了）。 再比如从小到大排好的 n 个数，从中找出等于 x 的那个。一种方法是按着顺序从头到尾一个个找，最好情况是第一个就是 x ，最坏情况是比较了 n 次直最后一个，因此最坏情况下的计算复杂度也是 O(n) 。还有一种方法：先取中间那个数和 x 比较，如偏大则在前一半数中找，如偏小则在后一半数中找，每次都是取中间的那个数进行比较，则最坏情况是 lg(n)/lg2 。忽略系数 lg2 ，算法复杂度是 O(lgn) 。 2 ，计算复杂性的排序： 根据含 n 的表达式随 n 增大的增长速度，可以将它们排序： 1 lg(n) n nlg(n) n^2 ... n^k (k 是常数） ... 2^n 。最后这个 2 的 n 次方就是级数增长了，读过棋盘上放麦粒故事的人都知道这个增长速度有多快。而之前的那些都是 n 的多项式时间的复杂度。为什么我们在这里忽略所有的系数、常数，例如 2*n^3+9*n^2 可以被简化为 n^3 ？用集合什么的都能解释，我忘了精确的说法了。如果你还记得微积分的话就想像一下对 (2*n^3+9*n^2)/(n^3) 求导，结果是 0 ，没区别，对不？ 2 ， P 问题：对一个问题，凡是能找到计算复杂度可以表示为多项式的确定算法，这个问题就属于 P (polynomial) 问题。 3 ， NP 问题： NP 中的 N 是指非确定的 (non-deterministic ）算法，这是这样一种算法：（ 1 ）猜一个答案。（ 2 ）验证这个答案是否正确。（ 3 ）只要存在某次验证，答案是正确的，则该算法得解。 NP (non-deterministic polynomial) 问题就是指，用这样的非确定的算法，验证步骤（ 2 ）有多项式时间的计算复杂度的算法。 4 ，问题的归约： 这 我该用什么术语来解释呢？集合？太难说清了 如果你还记得函数的映射的话就比较容易想象了。 大致就是这样：找从问题 1 的所有输入到问题 2 的所有输入的对应，如果相应的，也能有问题 2 的所有输出到问题 1 的所有输出的对应，则若我们找到了问题 2 的解法，就能通过输入、输出的对应关系，得到问题 1 的解法。由此我们说问题 1 可归约到问题 2 。 5 ， NP-Hard ： 有这样一种问题，所有 NP 问题都可以归约到这种问题，我们称之为 NP-hard 问题。 6 ， NP 完全问题 (NP-Complete) ： 如果一个问题既是 NP 问题又是 NP-Hard 问题，则它是 NP-Complete 问题。可满足性问题就是一个 NP 完全问题，此外著名的给图染色、哈密尔顿环、背包、货郎问题都是 NP 完全问题。 从直觉上说， P=NP=NP-Complete=NP-Hard ，问题的难度递增。但目前只能证明 P 属于 NP ，究竟 P=NP 还是 P 真包含于 NP 还未知。
标签: NPC
