来客网

科学院计算所胡宏:著名世界数学难题NP完全性问题被证明了

声明:本文转载自 「科技时空」, 或因排版与篇幅原因进行过编辑,内容未经本站独立核实,不代表本站立场、观点或建议。 如涉及版权问题,请联系我们,核实后立即删除。 [ 免责声明 ]

NP完全性问题是世界难题,实际上关于NP≠P的证明并不难,人们误解了它,它的证明竟然如此简单明了,证明的主要部分已经向SIAM杂志与《计算机学报》,投稿。

下面是关于它的正明,欢迎各路数学大侠对本证明提出各种批评。

引理一:用确定型图灵机判断某一个体a是否属于k个元素的集合 的时间复杂度为O(k)。(判定集合 中最小元素的问题与此类似)。

证明:用归纳法易证,在最坏的情况下我们必须比较k次,才能作出判断。

推论:用确定型图灵机判断某一个体a是否属于[0,power(2,n+1)]区间内的任意power(2,n)个二进制数的集合W计算时间复杂度为O(power(2,n)) 。也就是说判断一个元素是否属于一个元素的名字信息需用n+1位比特信息表示的集合中power(2,n)个元素的子集所需时间复杂度为power(2,n) 。(事实上该推论已经表明NP≠P )。我们把上问题叫做“属于判定问题”。

NP≠P的证明:power(2,n+1) 个二进制数需要n+1比特的信息表示,请注意属于判定问题中,我们要判断某一个体a是否属于[0,power(2,n+1)] 区间内的任意power(2,n)个二进制数的集合S时,我们至少需要对power(2,n)个数中的每个数访问n比特的信息,因为如果信息长度小于n就不足以表示power(2,n)个数了。小于power(2,n+1) 的二进制数可以用高度为n+1的二叉树表示如下:二叉树的左边为“0”,右边为“1”,从根到叶路径上的“0” 与“1”串形成一个二进制数。二叉树可以与n叉树互相转化。所有NP问题的解空间都可以表示成一棵n叉树(称为搜索树),无论用何种方法求解NP问题,至少要访问一条从根到叶的路径这样的路径,否则无法获得答案。如果在树的边上放上一个权值,从根到叶路径上的各边的权值之和为路径的代价,在这样的二叉树上寻找最小路径的问题是一个NP问题。具有power(2,n)个元素的集合的属于判定问题也可以看成是在上述搜索树上进行的,如果NP=P,则具有power(2,n)个元素的集合的属于判定问题的时间复杂度可以降为多项式复杂度,这就与引理或其推论相矛盾。证毕。

由上的证明可以看出,尽管power(2,n) 个元素的集合的属于判定问题是最简单的NP完全性问题,但它具有其他NP完全问题的一切特质。计算时必须在高度为n+1(或n)的搜索树上搜索。如果各条搜索路径完全相互独立,最坏的情况下的指数时间开销就可能出现,而这种最坏的情况无法通过多项式时间的搜索来排除,反之如果路径之间存在某种可预测的关联,即对集合中元素的分布有一定的了解,我们就有可能通过对搜索树的多项式时间搜索在访问多项式条路径后依据一定的概率找到解。

另一方面,从上面的证明可以看出,实际上一个问题是否为NP完全问题是相对的。本来属于判定问题是关于集合元素个数的P类问题,但我们如果换一个角度即从元素名字的比特数的角度分析它时,它就体现为NP完全性问题了;反之,如果以图的边为问题求解的起点,则Hamilton 路径问题是NP完全性问题,如果有一种计算装置以完整的路径计算单位,则Hamilton 路径问题是关于路径数的P类问题。

也就是说一个计算过程的时间复杂度所体现的特点与我们看问题的起点有关,这就提示我们如果我们改变计算单位的起点,我们就有可能把NP问题转换为P类问题。

评论 (0)