通俗解释 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 2 +…+ ξ x k ，其中 k 是常数。如果错误地将 k 理解成变量，就会混淆指数和多项式。例如组合和表达式 ( n 0 )+( n 1 )+…+( n k )+( n k+1 ) +…+( n n-1 ) +( n n )=2 n ，这里 n 是变量，此为 n 个元素从 0 取到 n 个的组合数之和。实际上这是是指数 2 n 的另一种表达形式，不是 P 与 NP 问题所说的多项式。 P 与 NP 问题从上个世纪 70 年代，史提芬 . 库克提出 NPC 类之后，学界已经认为只要能够找到一个 NPC 类问题的多项式时间解法，那么就证明了 P=NP 。近些年国外学者屡次发表 P ≠ NP 的证明，都未被承认。笔者认为这不是一个纯理论证明的问题，而是一个创造理论实现证明的实际依据问题。解决 P 与 NP 问题，最有力的关键是要找出 NPC 类某个问题的多项式时间算法，或者没有。由于 n 是趋于无限大的，这让后者的逻辑证明进入了死穴。 P 与 NP 问题国内研究的学者不很多，因而许多问题都不会与其关联。笔者深入研究了 SAT ，发现用限位数理论去分析逻辑变量的可选值，逐步消去那些只能取唯一值变量，消去结果为真的子句，如果合取范式有解，那么就可在不超过 O(n 4 ) 时间复杂度，即不超过 4 次多项式时间，可求出 3-SAT 满足解。 维基百科上有P/NP问题介绍，想了解更多可以去读。 2017-11-8
标签: 3-SAT
