计算复杂度研究现状

计算复杂性理论研究现状

摘 要

根据对多项式时间复杂性的存在算法,得出计算复杂性理论把问题按其复杂性分为三大类:存在多项式时间复杂性的问题;肯定不存在多项式时间算法的问题,即具有指数时间复杂性问题;未找到多项式算法，不证明不存在多项式算法。计算复杂性理论是计算机科学理论的一个重要组成部分,当代几乎所有重要的科学问题都与计算复杂性有关,如人工智能问题,认识极限问题等,这些问题都是当代科学前沿的一些重要但未解决的问题。计算复杂性理论正在被人们进行深入的研究,研究的焦点一般集中于NP=? P和设法解NPC问题上,随着计算复杂性理论研究的不断深入,计算机科学理论得到了飞速的发展。

关键词:多项式时间复杂性；NP类；NPC问题

1 图灵机(TM)

图灵机是一种重要的计算模型,是由英国数理逻辑学家A1M1Turing于1936年提出的。它的基本结构思想为1946年计算机的问世在理论上奠定了基础。图灵机不仅可以作为语言识别器,而且可以计算函数,其中,原始的是实现对整函数的计算。从读写带的条数来分,图灵机有一条带的图灵机和多条带的图灵机;从动作函数来分,图灵机有确定的图灵机和不确定的图灵机,不确定的图灵机同确定的图灵机的区别在于它的动作函数D是一个多值映射

从理论上说,有理数可以表示成自然数序偶,实数可以表示成自然数序列(其近似值为有限序列),而非数值信息通常可用自然数编码来处理。因此,图灵机可计算函

数包含了迄今为止所有的可计算函数。

图灵机是一种实际可计算的理想机,故图灵机的可计算问题是计算机中可计算性的理论基础,可计算理论早已发展成为一门独立的学科。

2 可计算函数

首先给出完全递归函数的定义如下。

定义211 若存在图灵机TM实现函数f的计算功能,而且对于任意一组输入(i1, i2,+, in),TM都能停机,则称函数f为一个完全递归函数。

定义212 一个函数f是可计算函数,当且仅当f是一个完全递归函数。对于可计算函数,可以设计算法进入计算,而且对于每一个输入,算法都能终止,并且输出计算结果。

3 计算复杂性

计算复杂性是计算机科学理论的一个重要组成部分,计算复杂性包括时间复杂性和空间复杂性。研究问题的计算复杂性是为了找出解决该问题而其复杂性又达到最低(阶)的算法,特别是使时间复杂性达到最低(阶)的算法。

定义311 对于一个问题Q,称其时间复杂性为T(n)(其空间复杂性为S(n)),若存在一个计算问题Q的图灵机,它以T(n)为时间界(以S(n)为空间界)。

时间复杂性一般分为多项式时间复杂性和指数时间复杂性两种,多项式时间复杂性是指可用多项式来对问题的计算时间界定,而指数时间复杂性是指可用指数来对问题的计算时间界定,常见的6种多项式计算时间函数及它们之间的关系是 O(1)

而常见的三种指数计算时间函数和它们之间的关系是

O(2n)

具有多项式时间复杂性的问题是可解的,但是具有指数时间复杂性的问题在实践中并不一定是可解的,这是因为求解该问题的算法可能需要极长的机器运行时间和极大的存储空间,使得在现有的计算机上根本就是无法实现,例如,货郎担问题(traveling salesperson problem,TSP)中,当问题规模(访问城市个数)为n,那么TSP共进行的比较操作次数

n(n-1)!/2-1,当访问的城市数为10个,计算机的运行速度为1Mflops(每秒一百万次浮点运算),则所需机器时间为0.118 s;而当访问城市为20个时,所需机器时间长达1929年,显然这个时间是无法容忍的,这类问题只能用近似方法或启发式方法求解。如果能将具有指数时间复杂性的问题转化为具有多项式时间复杂性,那就取得了一个可喜的成就。

4 P类和NP类

一个问题是否存在多项式时间复杂性的求解算法,是人们关心的问题之一,如果一个问题存在多项式时间复杂性的求解算法(即其计算时间(步数)可表示为输入量的多项式函数),那么这个问题就可以借助计算机来实现求解。反之,如果算法所需要的时间(步数)是输入量的指数函数,如T(n)=2n,那么当n很大时(如n\64),T(n)就是一个很大的数量,用计算机是无法在有效的时间内实现求解的。

定义411 用确定的图灵机(DTM)在多项式时间界内可求解的问题称为P类问题;用不确定的图灵机(NTM)在多项式时间界内可求解的问题称为NP类问题。

由于DTM是NTM的一种特殊情形,因此显然有PANP,但问题是是否有NP=P?

问题NP=? P的重要性是明显的,有许多问题(至少几百个),如等划分问题,布尔表达式的可满足性问题等,现已给出了多项式时间的NTM求解方法,但未给出多项式时间的DTM求解方法,如果NP=P,那么上述问题就都可以找出多项式时间的计算机算法。 NP=? P是当今计算机科学中有代表性的难题之一。至今未能证明NPXP,也求能证

明NP=P。美国克雷斯研究所悬赏100万美元对7个问题征解, NP=? P的问题列在7个问题之首。在20~21世纪之交,中国科协组织200位科学家写了一本书名为521世纪的100个科学难题6的书,NP=? P问题也列在其中。

5 NP-完全问题

NP-完全问题是计算复杂性理论中最重要的一部分,这方面的研究结果对于计算机算法研究和运筹学研究等方面的工作都是十分有用的。首先给出NP困难问题的定义 如下。

定义511 设一个问题Q1满足条件:PQINP都有Q

WQ1,则称Q1为一个NP困难问题。NP困难问题是求解/难度0(时间复杂性)不小于任意

NP类问题的一类问题。若Q1可以有多项式的时间界的求解算法,则任意一个NP问题都可以有多项式时间界的求解算法。

定义512 若问题Q1INP且PQINP都有QWQ1,则称Q1为一个NP完全(NPC)问题,记为Q1INPC。NP完全问题的意义在于:如果Q1INPC,则由于Q1INP,若Q1IP,就可以肯定所有的NP类问题都有多项式的确定算法。也就是说, NPC问题是NP类问题中最难的问

题。下列定理说明了NPC问题的意义。

定理511 设Q1INPC,那么NP=P当且仅当Q1IP。

定理511表明,如果能找到一个NPC问题Q1,对Q1找出了多项式算法,那么所有的NP类问题都存在多项式算法,即有NP=P。这样就把NP=P?的问题转化为对某一个(任意一个)NPC问题找出多项式算法的问题。

当然定理511还有另一层意思:只要证明其中某一个(任意一个)NPC问题不存在多项式算法,那么所有的NPC问题都不存在多项式算法,从而证明了NPXP。可见,对某

一个NPC问题给出多项式算法,或者证明某一个NPC问题不存在多项式算法成为回答NP=? P的关键问题。

从定义511和定义512看出,NPC问题是NP类问题中的NP困难问题,或者说是NP类问题中/最难0的一个问题子类,由于P类问题也是NP类的一个子类(这是相对不那么困难的一个子类)。如果能够找到NPC和P的一个交点(即找到一个问题Q1IPC且Q1IP),那么就会推出NPC=P=NP。为了寻找NPC和P的交点,人们首先着眼于寻找NPC的元素。1971年Cook找出了第1个NPC问题,从而证明了NPC问题是确实存在的,这被认为是一个划时代的结果。他证明了布尔表达式的可满足性问题是一个NPC问题,这就是著名的Cook定理。

定理512 (Cook定理)布尔表达式的可满足性问题是一个NPC问题。

在Cook定理之后,有人通过把布尔表达式的可满足性问题多项式归纳为命题演算舍取范围的可满足性问题,证明了命题演算舍取范围的可满足性问题也是一个NPC问题。现在已经找出的NPC问题已有300多个。

这样,如果某一个NPC问题确实存在于P类中,那么P类和NP类重合,即有NP=P。这一命题的巨大的意义在于现已证明像装箱、路径、调度等许多组合问题以及其他科学领域中的一大批问题都是NP完全的。NPC问题是NP类中最难的问题,如果对于NPC问题中任意一个问题存在有多项式时间算法,则整个NP类问题都存在多项式时间算法,从而也就证明了NP=P的命题。然而,这个命题至今没有得到证明。因此,计算科学家们大都认为NP完全问题不存

在有效的多项式算法,即有NPXP。于是,事实上就形成了所谓的NP=? P的问题。 NP=? P问题的研究受到科学家们的高度重视,并且逐渐形成了三个主要的学派.

(1)传统概念学派。传统概念学派坚持以图灵机、图灵可计算等传统概念来研究NP=? P问题,他们是这一问题研究的主流。这一学派提出了一些新方法、新思想,比如:关于布尔线路下界、多项式时间分层、多项式归纳、交互式证明系统、one-way函数和程序复杂性等研究,这些成果有力地加深了对NP=? P的研究。

(2)人工智能学派。因为大多数组合问题的算法都是NP完成的,在现实机器的存储资源和机器运行时间条件下,很难得到或根本得不到最优解。而在许多实际的应用问题中,令人满意解并非一定是最优解。所以,放弃寻求最优解,而去研究启发式搜索算法以及相应的概率分析。这种方法是以牺牲完全性换取高效率和满意解,它在人工智能的应用中取得了很好的效果。

(3)变革学派。随着人工智能和认知科学的不断深人发展,NP=? P问题又长期未能得到满意的解决,因此应突破传统的图灵计算等概念,探讨新的研究方法成为变革学派的主张。例如Clark提出不能把计算纳结为符号变换,应该研究形式符号系统和连续信号处理系统之间的关系,也有人认为人脑是一个开放式系统,计算机也应该是开放的,应该用开放的模型去计算。

6 结 论

(1)如果对某个NPC问题设计出确定算法,那么就证明了NP=P,即全部NP问题都是多项式可解的。看来做到这一点的可能性不大,过去许多算法工作者企图解决这个问题,都未取得成功。

(2)如果证明了某个NPC问题肯定不存在确定的多项式算法,那么所有的NPC问题也不存在确定的多项式算法。亦即说明了NPC问题是真正困难的问题。

(3)通过多项式归纳等手段继续发掘出一些NPC问题,扩大NPC问题的范围。 问题NP=? P是计算科学中引人瞩目的大课题, NPC问题的提出和研究就是为了最终解决这个问题,然而NPC问题的提出和所取得的成果虽然使NP=? P的问题向前迈出了一大步,然而最终的一步(也是最关键的一步)却历经30多年都未完成:即没有对其中某个NPC问题给出多项式算法,也没有证明某个NPC问题不存在多项式算法。NP完全问题是近20年来算法研究中最重要的理论发展,这方面的研究结果对于计算机算法研究和运筹学研究等方面的工作都是十分有用的。最近, Spielman和Teng提出了平滑复杂性概念及复杂性平滑分析方法,在理论计算机科学界引起了极大的关注,可以相信,随着计算复杂性的研究的不断深入,会促进计算机科学与理论

的飞速发展。

参考文献:

[1] 陈志平,徐宗本1计算机数学)))计算复杂性理论与NPC、NP难问题的求解[M]1北京:科学出版社, 20031

[2] 堵丁柱,葛可一,王洁1计算复杂性导论[J]1高等教育出版社, 20021