悬赏百万美元千禧难题有了新进展

美国克雷数学研究所于2000年悬赏100万美元求解的P/NP问题最近有了新进展。据维基百科说P/NP问题直接涉及到计算机科学和数学的方方面面（参见附录）。

什么是P/NP问题呢？

简单地说，能够用函数或映射方式有限次（多项式时间）求解的问题是P类问题，而能够用验证方法（关系）有限次得到解的问题是NP类问题。问，P=NP?

显然用函数或映射方法得到问题解的过程是确定性的，而用验证的方法求解过程是随机性的。我们可以将函数求解的过程看作是一种验证方法，因而可以认为P类问题就是NP类问题。反过来，NP类问题是否也是P类问题？这正是几十年来人们未曾解决的难题。

1971年斯提芬.库克提出了所有NP类问题都可以在多项式时间转化（归约）为某个特殊的问题，这个问题叫NP难（NP-hard），如果这个问题本身是NP问题，那么就称这个问题是NP完全问题（NP-complete）。

后来学术界承认了斯提芬.库克的观点，发现了许多所有NP问题都可以归约到的NP-complete问题（见图1）。由于NP完全问题是NP问题，因而只要找到一个NP-complete问题能够用函数或映射的方法经过有限次操作求出解，那么可以得出P=NP的结论。

图1  典型的NP-complete问题

近些年来，尽管人们发现了数以千计的NP-complete问题，然而2015年之前一直没有人能够找到某个NP-complete问题的多项式时间解法。有人预测，P/NP问题的解决至少还需要三十年，但想不到这个问题在2015年就有了让人们眼前一亮的结果。

NP-complete问题看似最简单的是3-CNF-SAT问题，一般称为3-SAT或3SAT。

把逻辑变量x的非运算用x’表示，逻辑变量间的或运算用“+”连接，那么3-CNF就是形如(x₁’+x₂ +x₃’) (x₁ +x₂+x₃ ) (x₆ +x₈ +x₁₀’)…(x_i +x_j’+x_k )…,由3个逻辑变量自身或者它的非运算组成的逻辑多项式（子句）的与运算表达式。这种表达式一般称为合取范式。

如果用f(x₁,x₂ ,…,x_n)来记3-CNF，那么3SAT问题就是求f(x₁ ,x₂ ,…,x_n)=1的解。

看起来3SAT仅仅是一个求n元函数值为1的解问题，然而长期以来人们却未找到它的解法，很多人都认为它的求解难度极大，包括克雷数学研究所。

谁都知道，n个变量的3SAT有解一定是一个n位的二进制数。如果我们将2ⁿ个n位的二进制数都一一带入f(x₁ ,x₂ ,…,x_n)=1的左端验证，一定能够得到是解，或者不是解。因而3SAT是一个典型的NP问题。遵从斯提芬.库克理论的人已经证明了3SAT是一个NP-complete问题（这方面的证明较复杂，在此不谈）。因而只要我们能够用函数或映射的方法，有限次一步步地推定出f(x₁ ,x₂ ,…,x_n)=1的解，那么是否P=NP的问题不就解决了？

2014我国的一位数学出身计算机专业退休的教师，凭着兴趣进入了3SAT这一问题研究，提出了看似非常简单的“子句消去法”来求解。经过一年多的曲曲折折，竟然让他找到了用子句消去法求解3SAT的方法。他相信，任何一个人见到这种3SAT求解方法之后，不能不叫人发出“原来这么简单！”的感叹。

他将变量自身用1表示，将变量的非运算用0表示，将3-CNF列成了表1的格式，所求解放在表头上方。遵从子句消去法的函数算法，不论多少个变量（有限多），都能够一次性逐步求出3SAT的满足解。

表1  3-CNF子句的表格式

子句消去法是运用子句中某项的值为1，消去该子句不影响剩余3-CNF=1的解的原理，逐步求出全体n个变量取值的向量解。

子句消去法规则简单。变量相同的子句在表中形成了子句块。可以证明有8个子句组成的子句块存在时3SAT一定无解；有一个变量值确定，剩余的两个变量形成4种不同类型子句的子句块存在，或者两个变量值确定，剩下一个变量有不同值，3SAT都无解。

依照子句消去法上面求解的这些原则，对没有8个子句的子句块组成的3-CNF数值表，进行如下步骤的操作可以求出满足解。

（1）将所有子句块中一个变量有4个相同值的变量设定其值，消去变量值相同的子句；

（2）确定剩余子句中有唯一解的剩余子句块解，并消去变量值相同的子句（特别是3个子句的剩余子句块）；

（3）最后设定所有多解的剩余子句块的解。

（4）求解中，如果前面处理的都是变量唯一解的情况，遇到了不能回避的无解情况，那么3SAT无解。

子句消去法用Excel操作十分方便。

如果您有兴趣探讨，可参考http://blog.sciencenet.cn/blog-340399-928224.html，亦可联系accsys@126.com或accsysuibe@uibe.edu.cn

2015-12-6

【附录：摘自网上百度文库huangyz59420《对P和NP问题的介绍》上传于2010-12-28】 

假如P=NP,世界将会怎样？

P是否等于NP是计算机科学领域中最突出的问题，在千禧年七大难题中排在首位。虽然人们大多相信P问题不等于NP问题，但人们目前既不能证明它，也不能推翻它。科学家们普遍认为P≠NP是有原因的，让我们来看一看，如果哪一天科学家证明了P=NP，那这个世界将会变得怎样？

l         已知的NPC难题将全部获解，这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度；同时，当空接龙、扫雷、数独等经典游戏也由于获得了多项式的是否而在很大程度上失去了意义。

l         算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样，将成为一种纯粹锻炼思维的游戏。

l         一些新型的自动编程语言将出现，并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。

l         困扰人类已久的自然语言处理问题将被一举攻破。考虑这样一个最优化问题：输入一大批语句样本，它们有的符合语法，有的不符合语法；寻找一个最简单的算法，将这些语句输入这个算法时，算法能正确得出它是否符合语法。

l         类似地，所有人工智能问题都将得到解决。我们只需要向计算机提交足够多的情境以及与之对应的正常人反应，计算机就可以找出一种能正确生成出这些反应的最简单算法，完全模仿人类的行为。

l         数学证明可以完全交给计算机来处理。寻找一个反例和验证一个反例变得同样简单，一切错误的猜想都将瞬间被推翻。事实上，寻找一个数学证明和验证一个证明的正确性也变得同样简单，因此一切正确的命题也能够瞬间找到一个最简单的证明。

l          发明任何新的密码算法都是徒劳的。计算机可以根据一大批明文密文样本推算出生成密文的算法（只要这个算法是多项式的）。现有的密码学体系彻底崩溃。