姜咏江

P与NP问题是美国克雷数学所2000年悬赏百万美元的七大世界难题之一。

1.        什么是P与NP问题？

下面这段话是从维基百科的p与np问题的绍中摘录的。

In this theory, the class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose 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 open question in theoretical computer science concerns the relationship between those two classes: Is P equal to NP?

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

注意定义中的计算和验证这两个词。计算机就是顺序确定执行的机器。确定问题是根据输入条件来回答是与否的问题,而验证问题是回答可能是，可能否的问题。计算是从输入条件通过某种规则，确定地逐步推导出问题结果的过程，计算可以确定问题是否有解。按照规则正确推导，如果问题有解，计算就一定能够求出；而验证是一种检验的过程，这种过程从可能的结果出发，检查认定的结果是不是符合问题的条件，是否满足问题要求的过程，这一过程具有是或不是的随机性。验证与计算的根本不同，在于一次验证不是解，并不能确定问题无解还是有解。因计算具有确定的规则方法，这种规则方法保证了问题通过计算就可以确定有解或是无解。

给出一个正整数，判定是不是素数。这个问题可以通过给出的数，进行一次确定的计算就可以给出答案，不需要更多的重复来作。这是p类问题。P类问题的结果是通过计算求出来的，计算得到的正确结果一定满足问题的条件，因而p类问题自然也就是np类问题。

有些问题可以预先猜测到“可能解”，依据问题条件通过验证过程的计算，能确定是否是问题的答案。换句话说，计算的过程带有概率成分，这类问题就是NP类问题。

例如，有集合｛1,-5,123,45,-7,-10,6｝中有没有和为151的子集？这是一个还没有找到一次计算就能够确定的问题。一般需要多次反复选择子集，然后计算。最坏的情况是要把全部子集找出来，这要选择操作C₇⁰+ C₇¹+ C₇²+ C₇³+ C₇⁴+ C₇⁵+ C₇⁶+ C₇⁷=2⁷=128次。但如果随机选择了｛123,45,-7,-10｝这个子集，马上可以验证是正确的。这个问题输入的规模是n=7个数。如果将n个数的数集全部子集找出来验证，那么需要进行2ⁿ次验证。这种先做出子集，再找结果的2ⁿ次算法，是n的指数型重复操作的方式。如果这个问题改成要求“4个数的和为151”，那最坏的情况只要找出7个数中的4个数的子集，找出4个数的子集的操作只要重复进行C₇⁴=35次就可以了。一般化，如果原集合有n个数，求k个数和的集合子集问题，就应该有C_n^k=n(n-1)(n-2)...(n-k+1)/k!次求子集的过程。k是一个不变的正整数，n是一个大于等于k的变量，组合数C_n^k是一个k阶多项式。

从n变大增长的过程中有y=2ⁿ和z=a_nn^k+ a_n-1n^k-1+...+ a_n-k+1n^n-k+1这两种问题的函数表达式。考虑到当n增大到一定程度时，y的增长速度会远远超过z的增长速度，这就引入了所谓的指数时间复杂度和多项式时间复杂度的概念。n是输入数据的数量，称为输入规模。一般，多项式时间复杂度用O(n^k)来记，不考虑多项式的系数和低阶项。

属于幂底数比2大的指数形式，规模增长时，函数增长更快，所以问题研究常以y=2ⁿ这个指数函数说事。从C_n⁰+ C_n¹+...+ C_n^n-1+ C_nⁿ=2ⁿ的关系来看，只有当k是确定的数，才可以区分出O(n^k)和O(2ⁿ)。

到底np类问题能不能是p类问题，这要看能否将一个指数形式过程的时间复杂度算法，找到一种多项式时间复杂度的算法替代。如果找到了一个，就否定了P≠NP的假定。当然，必须能够肯定所有的NP类问题，都能够找到多项式时间复杂度算法，才能够说明NP类问题也是P类问题。

non-deterministic machine直译是不确定型机器，实际上是说非确定型图灵机。简单地说就是一种多路分支机构的层次计算机群。每个层次的计算机都接续上一个层次计算机的多个输出的一个做为输入，最终叶上的计算机得到的是全部可能值对错的结果。这种计算机群是按照指数型增长计算机的，实际上当n是有限数的时侯可以认为存在，全体构成了一种森林结构的计算机群。由于这种计算机群能够将所有确定计算的结果在多项式时间内完成，因而在时间上来说，等同于去掉了概率型的反复，实现了确定计算。

non-deterministic machine在规模n不断增大的时侯，必然突破人类可能获得资源的界限，实际上n大到一定程度的非确定型图灵机根本就不可能存在，只有理论上的探讨价值。

究竟NP类问题能不能用一台计算机在多项式时间内确定地计算出肯定的结果？P是否等于NP？且看下回分解。

2016-11-17