通俗解释P与NP这个世界难题

姜咏江

       与人工智能关系重大的P与NP问题，是美国克雷数学所千禧年以百万美元大奖悬赏的七大难题之一。通俗地讲，就是“最坏在指数时间可以猜测验证答案的问题，是否可以在多项式时间求出一个正确答案”。前类问题称为NP，后类问题称为P，一般表示为P?=NP。

例如，最多由3个不同逻辑变量值的或运算组成的多项式叫子句，若干个子句的与运算叫合取范式。问，能否找到n个变量的一组值使合取范式的结果为1？

这个实例叫布尔可满足性问题，也叫3-SAT问题。3-SAT问题直接涉及到集成电路可靠性分析等。人们已经证明了，如果3-SAT可以在多项式时间求出答案，那么P=NP就成立。

每个子句变量值不多于k个的子句所成的合取范式叫SAT。能够将其它NP问题，通过多项式时间转化为SAT问题的一类，称为NP完全问题，简写成NPC。由于所有SAT都可以转化成3-SAT，所以谁能够解决3-SAT或NPC中任何一个，那么就等同证明了P=NP。

NPC问题有很多，典型的还有子集和问题、哈密顿回路问题、背包问题、邮差问题、图的顶点覆盖问题、因素效果分析问题等。

什么是指数时间？就是事情的解决是概率性的。即一次处理得到的结果不一定对，需要验证才能够知道。这多体现为重复进行某种操作才可以得到正确答案。

什么是多项式时间？就是一次性处理就可以得到正确的答案。

变量x多项式的数学表达为：a+bx+cx²+…+ξx^k       ，其中k是常数。如果错误地将k理解成变量，就会混淆指数和多项式。例如组合和表达式(ⁿ₀)+(ⁿ₁)+…+(ⁿ_k)+(ⁿ_k+1) +…+(ⁿ_n-1) +(ⁿ_n)=2ⁿ，这里n是变量，此为n个元素从0取到n个的组合数之和。实际上这是是指数2ⁿ的另一种表达形式，不是P与NP问题所说的多项式。

P与NP问题从上个世纪70年代，史提芬.库克提出NPC类之后，学界已经认为只要能够找到一个NPC类问题的多项式时间解法，那么就证明了P=NP。近些年国外学者屡次发表P≠NP的证明，都未被承认。笔者认为这不是一个纯理论证明的问题，而是一个创造理论实现证明的实际依据问题。解决P与NP问题，最有力的关键是要找出NPC类某个问题的多项式时间算法，或者没有。由于n是趋于无限大的，这让后者的逻辑证明进入了死穴。

P与NP问题国内研究的学者不很多，因而许多问题都不会与其关联。笔者深入研究了SAT，发现用限位数理论去分析逻辑变量的可选值，逐步消去那些只能取唯一值变量，消去结果为真的子句，如果合取范式有解，那么就可在不超过O(n⁴)时间复杂度，即不超过4次多项式时间，可求出3-SAT满足解。

维基百科上有P/NP问题介绍，想了解更多可以去读。

2017-11-8