姜咏江

美国克雷数学所悬赏百万美元的千禧难题，P与NP问题是一个概念难懂的极其重要的问题。理解好这个概念，对快速解决NP类型问题十分有帮助。

1.     什么是问题？

所谓问题是由三部分组成的：输入、限制条件和结果。其中限制条件是确定的，而输入和结果都是可变的，而且输入和结果都要受到限制条件的约束。

2.     什么是判定问题？

所谓判定性问题，就是一个问题的解决结果可能不止一个，之中有对的，也有错的。可以通过验证的方法确定“是”与“否”。

什么是验证？就是将“认定的”结果放到问题条件当中检验，满足条件为“是”，不满足条件为“否”。因而验证过程本身就是一个判定问题。

3.     什么是多项式函数和指数函数？

变量x的表达式形如y = a₀x⁰+a₁x¹+...+a_kx^k,其中a₀,a₁,...,a_k和k都是常数，且k是正整数。

与多项式不同，变量x形如y=ac^tx的表达式就叫单一指数型函数，其中a,c,t都是常数，一般c≥2。可以将单一指数函数用“+”号连接起来，这种函数叫指数多项式函数，为了与多项式函数区别，就叫指数函数。

4.     p与NP问题中的多项式时间和指数时间复杂度

如果求解问题结果的基本动作总和可以表达成多项式函数，就称之为多项式时间复杂度；而只能表达成指数形式的，就称之为指数时间复杂度。

例如, 求n个元素集合的全部子集的基本动作总和，可以表达成2ⁿ的指数形式。但是求n个元素集合的5个元素的子集的基本动作总和，可以表达成从n个元素中取出5个的组合数，即C_n⁵=n(n-1)(n-2)(n-3)(n-4)/5!，这就是一个变量n的多项式。

可见相同的事情由于约束条件不同，解决问题的时间复杂度也可能不同。

5.     哪类问题一般是指数时间复杂度？

求n个元素集合的所有子集，无论如何得将每个子集求出。这些动作总和可以用

C_n⁰+C_n¹+ C_n²+...+ C_n^n-1+C_nⁿ=2ⁿ的形式表达。虽然等号的左面形式上像个多项式，但只是指数函数2ⁿ的分解表达形式而已，它与多项式的根本区别是“选取数不是常量”。如果有问题是求“不多于k个元素的子集，k<n且不随n改变”，则有C_n⁰+ C_n¹+ C_n²+...+C_n^k-1+ C_n^k就是一个多项式了（例如k=5）。

这个例子告诉我们，多项式时间中的常数k很重要，如果k是变量，就不是多项式了。

这个例子指出：指数时间复杂度问题，如果给定一定的约束条件，就可能转化成多项式时间复杂度的问题。

这个全部子集问题是不能够在多项式时间内验证的，因为要验证其全部子集的正确性，就必须检验2ⁿ个子集，要做2ⁿ个基本动作。一切结果呈现输入规模n的指数形式变化的问题都是关于n计算量大的问题。但这类问题的约束条件是“多项式时间内可以验证”就可能使原本指数类时间求出解的问题，转变成多项式时间内求出。不要将指数时间复杂度算法问题和NP问题混为一谈。

这就是下面NP问题定义中为什么要提“多项式时间内验证”的原因。

6.     P与NP问题的定义

维基百科上如下给出了P与NP问题的定义：

Inthis theory, the class P consists of all those decisionproblems (defined below) that can be solved on adeterministic sequential machine in an amount of time that is polynomial in the size of the input; theclass NP consists of all those decision problemswhose positive solutions can be verified in polynomial time given the right information,or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.^[5] Clearly, P⊆NP. Arguably the biggest openquestion in theoretical computer science concernsthe relationship between those two classes: Is P equal to NP?

译成中文：

在这个理论中，复杂度类P包含所有那些，可以由确定型顺序执行计算机依据输入规模，在多项式表达的时间内能够计算出来的判定问题；类NP由所有那些可能解，可以在多项式时间内通过验证来判定是否是解的问题组成，或者等效的说，那些解都可以在不确定型机器上通过多项式时间找到。显然，P类问题包含在NP类问题中。很可能，计算理论最大的未解决问题就是关于这两类问题的关系: P和NP相等吗?

没有点专业知识肯定会一头雾水。这里还要解释一下什么是“计算”和“不确定型机器”。

简单地说，“确定型顺序执行”意思是每一步执行“输入确定，这一步的结果就确定，不会出现多个结果”。一个处理器的计算机都是确定型顺序执行计算机（你就可以理解成现在使用的电脑）。关于计算歧义太多。我们可以理解成“按照已经确立的规则，能够逐步求出问题结果”的过程。

请注意，P与NP类问题都能够计算完成！只是P类问题是在多项式时间之内计算出结果。

7.     深入理解NP

直到下面这句话之前，或许你已经明白了什么是P和NP问题了。定义中补充的这句话就显得十分专业了。

“或者等效的说，那些解都可以在不确定型机器上通过多项式时间找到。”

所谓不确定型机器，实际上是分支结构确定型多结果计算机群。不确定的意思是每个操作步的一个输入要产生不止一个结果。而这些结果中的每一个，又是下一个操作步的输入。这样将每一个操作步输出的结果做为输入，都安排一个确定型产生这一步全部结果的机器来完成前一步生成的工作。如此组织的计算机群就是不确定型机器。

显然，不确定型机器能够在多项式时间计算出最初一次输入的全部结果，故称“在多项式时间找到”。以每次操作都产生2个结果为例，那么n个操作步，就会需要这样的机器2ⁿ个组成的群。这里的“找到”应理解成出现，而不是再一个一个去找。

所谓非确定型图灵机就是指这样的机器，实际上当操作步骤不断增大的时侯，这种非确定型图灵机根本就不会存在。因而非确定型图灵机只是一种“神谕计算机”而已，是指数型时间复杂度的一种替代的抽象。

8.     NP完全与NP难问题

NP类问题是问题解可以在多项式时间验证的，能不能找到方法在多项式时间内将满足条件的解计算出来？这是解决P与NP问题的要害之处。有一类问题都是多项式时间可验证解的问题，而且它们之间可以在多项式时间之内相互转化，这就是NP-complete问题。

什么是NP-complete问题由两条决定。

（1）它本身是一个NP问题；

（2）所有的NP问题求解都可以在多项式时间转化成它来求解。

不管一个问题的解是否是可验证的，即不满足这里的（1）条，但满足（2）条的问题，称为NP-hard问题。

实际上，很久一直没有找到任何一个NP-complete或NP-hard问题的多项式时间算法，即可在多项式时间内求出其中任何一个的解。

9.     猜测验证

在P与NP问题中有一个重要的概念人们并没有给出定义。这个概念就是验证。

数学验证是将计算得到的结果放到题目约束条件中，看看是否满足条件的过程。

验证过程最有戏剧性的是猜测验证。猜测验证变成了一个概率问题，从而充满了不确定性。由此观之，NP问题可能被理解成一类概率计算问题。只要我们知道或掌握这类问题的概率空间，就可以通过概率的方法（多次试验）分析某个结果（事件）发生的可能性大小。这这方法叫概率验证。NP问题提到的验证是逻辑判定的是与非的判定过程，是一次性的过程，不是概率验证。

在这种非概率意义之下，NP的定义中才提到“所有那些可能解”的验证问题。不是猜测验证的主观性问题。注意，“所有那些可能解”。

10. P与NP问题的进展

有人同意NP是多项式时间可验证问题的意见，也有人反对，说这就是P问题。例如定义中“所有那些可能解”不能理解成验证一个就完事。前面提到的集合的全部子集，若随便把几个元素组成集合，立即就可知是不是这个集合的子集，这不算。全部子集的验证就不是多项式时间能够解决的问题了。

概念上的争论，有时因为对某些基础概念的理解不同会产生歧义，倒使问题变得模糊了。解决P与NP最好的办法就是解决实际例子。找到一个NP-complete或NP-hard问题的多项式时间算法，那是证明P=NP的最有利证据。

本人的子句消去法完成了SAT这个典型的NP-complete问题的多项式时间求出满足解的方法。并将图用数码0和1表示成二维表，运用子句消去法的方法，完成了在表上进行图的顶点覆盖、团等图系列问题求解，其时间复杂度都不超过O(n³)。已将论文放到了arXiv.org，算是新思路放炮。

解决P与NP问题，需要数学和计算机理论方法很好的功底，二者缺一不可。例如HP的专家级程序设计师，将其P≠NP的证明写了一百多页，显然不是数学方法的精髓，因而难免出现证明漏洞。

P与NP的最好的证明应该是精炼的数学证明方法，切实可行的计算机算法。而这些，目前最好要落实到实际公认的例子解决当中。

还是那句话：将复杂的问题弄简单了，那是本事！将简单的问题弄复杂了，那是蒙人！

用这句话判断国外的那些知名科学家也一样适用。

2017-2-1