wingss的个人博客分享 http://blog.sciencenet.cn/u/wingss

博文

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

已有 4872 次阅读 2015-3-3 23:34 |系统分类:科研笔记| office, style, center



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

 

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

 

摘要: 我们将从多项式函数的加法运算的角度出发,来探讨P vs. NP问题。根据kk<=n)个关于n的多项式函数的和是否还是多项式函数,我们提出了两个相互矛盾的命题。如果认为k个关于n的多项式函数的和总是多项式函数,那么根据这个命题可以证明P=NP;而如果认为存在某k个关于n的多项式函数,它们的和是指数函数,那么根据这个命题可以证明P=NP。进一步地,这两个命题分别是P=NPP=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的多项式函数,其中kn。令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:数学归纳法是正确的。

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

 

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

 

具体来说,根据数学归纳法,首先易知Cn1是多项式函数;设对于任意的k (kn/2)Cnk是多项式函数,根据引理1Cnk+1=Cn-1k+Cn-2k++Ckk,而CkkCk+1kCn-1kCnk,所以可知CkkCk+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,我们只需证明Cn1Cn2,…,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)的判断问题,不妨假设Iin

我们定义问题ПП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不成立,那么根据定理2P=NP,矛盾。得证。

 

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

 

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

 

6 结论

 

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

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

 

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

 

 

 



https://blog.sciencenet.cn/blog-2446134-871706.html


下一篇:P≠NP——基于认知的视角

1 姜咏江

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-12-8 00:15

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部