P vs. NP 问题——一个有趣的视角

P vs. NP问题是一个在数学与理论计算机领域关注度很高的问题。这个问题是我在读研究生的时候从导师那里了解到的。由于感觉这个问题很有趣，我在工作后依然关注它，并有了自己的一些认识。现在，我大胆地把我的认识写出来，望各位前辈同行批评指正。证明过程有些粗糙简单，请多多包涵！

摘要： 我们将从多项式函数的加法运算的角度出发，来探讨P vs. NP问题。根据k（k<=n）个关于n的多项式函数的和是否还是多项式函数，我们提出了两个相互矛盾的命题。如果认为k个关于n的多项式函数的和总是多项式函数，那么根据这个命题可以证明P=NP；而如果认为存在某k个关于n的多项式函数，它们的和是指数函数，那么根据这个命题可以证明P！=NP。进一步地，这两个命题分别是P=NP和P！=NP的充要条件。

1. 二项式定理的一个性质

在给出证明之前，我们先来回忆一下二项式定理（或杨辉三角）：

(a+b)n=Cn0an+Cn1an-1b+Cn2an-2b2+…+Cnnbn

我们有下面的引理：

引理 1 对于任意的整数k (0<=k<=n-1)，Cnk+1=Cn-1k+Cn-2k+…+Ckk。

证明：Cnk+1=Cn-1k+Cn-1k+1=Cn-1k+（Cn-2k+Cn-2k+1）=……=Cn-1k+Cn-2k+…+（Ck+1k+Ck+1k+1）=Cn-1k+Cn-2k+…+Ckk。

2. 一个有趣的矛盾

现在我们来看一个有趣的矛盾。设h1(n), h2(n), …, hk(n)为k个任意的关于n的多项式函数，其中k≤n。令H(n)=h1(n)+h2(n)+…+hk(n)。这时，我们问H(n)是关于n的多项式函数还是指数函数？注意到H(n)≤kmax{hi(n)}≤nmax{hi(n)}，而max{hi(n)}显然为指数函数，所以，H(n)应该是一个多项式函数（其中，max{hi(n)}指h1(n), h2(n), …, hk(n)中的最大者）。但是，H(n)真的总是一个多项式函数吗？实际上，如果我们承认下面的三个命题，那么我们便得到了一个矛盾。

命题1：多项式函数和指数函数是两个不同的概念。

命题2：数学归纳法是正确的。

命题3：H(n)总是多项式函数。

我们不妨假设本文中的n总是偶数。首先，容易证明Cnn/2≥2n/2，从而Cnn/2是一个关于n的指数函数；但是，我们通过命题2和命题3也可以证明Cnn/2是一个多项式函数。

具体来说，根据数学归纳法，首先易知Cn1是多项式函数；设对于任意的k (k≤n/2)，Cnk是多项式函数，根据引理1，Cnk+1=Cn-1k+Cn-2k+…+Ckk，而Ckk≤Ck+1k≤…≤Cn-1k≤Cnk，所以可知Ckk，Ck+1k，…，Cn-1k均是多项式函数，进而根据命题3可知Cnk+1也是多项式函数。于是我们用数学归纳法证明了Cnn/2竟然也是一个多项式函数！！！与命题1矛盾！！！

问题出在哪儿了？我们认为，命题1和命题2都是很好接受的。问题应该出在了命题3上面。实际上，如果承认命题3，那么可以证明P=NP（当然了，证明过程可能比较可笑啦！），而如果不承认命题3，那么是可以证明P！=NP的。

3 接受命题3的情形

如果承认命题3，我们可以很容易证明P=NP。

定理 1 如果接受命题3，那么P=NP。

证明：我们知道，要证明P=NP，只需证明某个NPC问题存在多项式时间的算法即可。最大团问题即是一个经典的NPC问题。

给定一个具有n个顶点的图，我们可以运用穷举法求解出最大团。即，分别检查是否存在具有i (i=1,2,…,n)个顶点的团。显然，具有i 个顶点的子图最多有Cni个。因此穷举法最多需要检查Cn1+Cn2+…+Cnn个子图，而在判定每个子图是否为团只需多项式时间，因此我们只需证明Cn1+Cn2+…+Cnn为关于n的多项式函数即可。根据命题3，我们只需证明Cn1，Cn2，…，Cnn均为多项式即可，注意到Cnk=Cnn-k，(k=0, 1, …, n/2)以及第2节中用数学归纳法对于Cnn/2为多项式函数的证明，定理得证。

当然，这个证明实际上是有些荒谬的，因为，Cn1+Cn2+…+Cnn就不是多项式的。但如果我们承认了命题3，在形式上确实是可以得出这样的结论的。您说是不是？？？

4 不接受命题3的情形

如果我们不接受命题3，这时，存在某k个多项式函数h*1(n), h*2(n), …, h*k(n)，使得H(n)为指数函数，其中H(n)=h*1(n)+h*2(n)+…+h*k(n)。在这种情形下，我们可以证明P！=NP。

定理 2 如果不接受命题3，那么P！=NP。

证明：实际上，要证明P！=NP，只需构造出一个问题П，使得∏属于集合NP且∏不属于P。  

我们知道一个判断问题的返回结果为“是”或“否”。设Пi为一个输入为Ii且时间复杂度为h*i(n) (i=1, 2, …, k)的判断问题，不妨假设Ii≤n。

我们定义问题П：П1,П2,…,Пk的返回结果中是否有一个“是”。（注意，问题П的输入为I1+I2+…+Ik不超过n2）

我们首先证明П不属于P。实际上，注意到I1,I2,…,Ik是相互独立的输入信息，任意的确定性图灵机在最坏情形下都需要检查全部的返回结果，需要的时间复杂度为h*1(n)+h*2(n)+…+h*k(n)=H(n)，为指数函数，于是П不属于P。

现在我们证明П属于NP。对于非确定性图灵机，它只需检查k个返回结果中的一个就可以了，需要的时间复杂度为多项式，于是П属于NP。定理得证。

5 进一步讨论

实际上，根据定理1和定理2，我们很容易得到下面两个推论。

推论1 P=NP的充要条件是命题3成立。

证明：根据定理1，充分性得证，因此下面只需证明必要性。实际上，如果命题3不成立，那么根据定理2，P！=NP，矛盾。得证。

推论2  P！=NP的充要条件是命题3不成立。

证明：证明过程与推论1类似。

6 结论

我们从多项式函数的加法运算的角度出发，探讨了P vs. NP问题。得到的结论是：（1）P=NP的充要条件是命题3成立；（2）P！=NP的充要条件是命题3不成立。

但是，我们仍然很难理解命题3的成立与否。或许，我们本不应该把多项式函数和指数函数对立起来。佛说，分别心产生烦恼。他说的可能是有道理的。

   最后，衷心感谢您对本文的关注与意见！！！祝您身体健康，工作顺利，阖家欢乐！！！