计算复杂性-资料搜集

计算复杂性一、引言计算问题，应该是一种从人类有文明起便一直纠缠着人类的问题；为了解决这些问题，人类需要进行计算，需要设计算法。显然，如果时间是无限的，计算机器性能也是无比的，那么选择什么算法并不是问题；但这不可能。人类计算的时间是有限的，人类的计算设备也不是万能的。因此，我们需要评判一种算法的复杂性。那么，计算复杂性到底是什么，它的意义是什么，它的进展如何，应用如何，本文试图进行一部分回答。二、相关概念1.计算复杂性、时间复杂性、空间复杂性：计算复杂性包括两个方面：时间复杂性，空间复杂性。时间复杂性反映了问题计算所需的时间耗费,一般是用计算的运算次数来衡量。空间复杂性则代表进行计算需要耗费的存储空间。例如，我们C语言作业的在线测评系统之中，会有内存和用时的要求；这两个方面分别体现了空间复杂性和时间复杂性。2.多项式时间、指数时间：多项式时间指的是一种算法的时间复杂度可以用含有n的一个多项式表示。这种情况下一般把操作数作为时间复杂度的衡量标准。而指数时间指的是一种算法的时间复杂性不能够用多项式进行表示。指数时间的算法效率较低，而且随着n的增大用时显著增加，被认为是相当于不存在的算法。3.确定性图灵机、非确定性图灵机：两者都为图灵机模型；但是确定性图灵机在一定的条件下，只会选择一种操作；而非确定性图灵机则会根据生成的（伪）随机数在多种方法中选择一种进行。4.P问题、NP问题、NPC问题：NP是指“在非确定性图灵机上有多项式时间算法的问题”的集合，而P是指“在确定性图灵机上有多项式时间算法的问题”的集合。另外一种表述是，P问题在多项式时间内可以解决，而NP问题在多项式时间内可以得到检验。P问题是NP问题的特例，而往往NP问题都被视作【但未被证明为】“不可”解决的问题。经过多项式变换能够变成所有NP问题的问题称为NPC问题。三、特色思想进行问题求解时，人们往往会关心：1.这个问题能否被算法求解；2.求解问题的过程需要消耗什么？而这正是计算复杂性研究的内容。科学家们将计算复杂性分解为时间复杂性和空间复杂性，分类进行研究。同时，由于我们的资源、时间都是有限的，复杂性过高的问题，也就成了实际上的无解问题。因此科学家们用操作数目表示时间复杂性，并将时间复杂性分为多项式时间和指数时间。多项式时间内的问题容易解决，而指数时间的问题则可以视作不能解决。而后，科学家们又通过对不同算法进行考察，认为算法可解决的问题大体可以分为两类，一是多项式时间问题，一是指数时间问题。还有一些问题，虽然能够在多项式时间内进行验算，却未被证明能在多项式时间中解决；这些问题在实践中也被认为是不可解决的问题。理解了这一点之后，计算者们采取了新的策略去应对问题。有的人仍然坚持研究最完美的算法，并为此继续探讨算法的转化，或者试图证明哪些算法是不可行的，那些算法可以。一些人认为，既然求最优解会消耗大量资源，那么应该着眼于寻找与最优解的差距可以接受的“可行解”，并由此设计出许多折衷性质的算法，如“贪心”算法。另外的一些人同样从现实生活出发，专注于问题的一些特殊情况，探讨这些更具有现实意义的特殊情况能否被解决。还有人转向了其它的计算模型，以求高效而准确的得到答案。显然，计算复杂性的研究产生的影响，远超出它原本的范围。除了理论的研究，计算复杂性的探索也影响到了许多应用领域。除了最直接的计算理论，包括运筹学、金融学、人工智能、软件设计等方面学科也或多或少应用到这些新的理论，借助这些理论寻找新成果，检验目前的模型。四、特色思想的原始叙述求解同一个数学问题可以有不同的算法。如果有多个算法求解同一个数学问题,如何对它们进行比较,以便从中找出求解的有效算法?如何评价或衡量一个算法的优劣程度?这些问题无论在理论上还是在实践上都是十分重要的。算法分析是对几种算法乃至几类算法进行比较,比较其复杂性以及实施是否方便,从而确定能否较好利用所指定的计算机的特性。在串行计算机上运行的算法常用加、减、乘、除运算的次数多少来评价,而在并行计算机上运行的算法就不能简单地以四则运算次数来衡童,算法的计算复杂性(Computationalcomplexity)也称复杂度,是衡量算法计算复杂度的尺度。使用最普遍的评价标准往往是一个算法所需要耗费的计算时间和所占用的空间(处理机台数或存储单元数)。如果一个算法所需要的时间或空间,比另一个求解同一问题所需要的时间或空间少,就可以说这个算法比另一个算法好。无论是从时间方面考虑还是从经济方面考虑,人们总是希望使用效率高的算法。这个原则既适用于串行算法,也可用来评价并行算法。时间和空间已成为评价算法好坏的两个重要方面,也是算法设计者长期追求的目标。这样,算法的计算复杂性有时间复杂性和空间复杂性。人们常用这两种复杂性来描述一个算法的特殊需要性能,宏观地评价该算法的质量。……按算法论和计算复杂性的观点,现有的问题大致可分为三类:第一类是无算法的问题。如著名的哥德巴赫猜想“费马猜想”均属这一类。所谓猜想是由人们的直观或直觉仁的初步判断认为可能成立,而又未经严格证明的命题,猜想若被通过严格的数学方法来论证,经过研究推导,被证明了的猜想,就直接变成定理。所以一个好的、深刻的猜想,往往成为数学家们长期研究的课题。如地图的着色中,有所谓“四色猜想”困扰了人们一百多年,70年代终于在计算机的帮助下,成功地得到证明,使“四色猜想”变成了“四色定理”。第二类是有以多项式时间算法存在的问题,被称为p类问题(P是多项式英文polynomial的第一个字母)。这一类问题是大量存在的。例如最短路程问题(在一个网络图中求给定两点之间的最短路程)的迪克期特拉(Dijksta)算法是O(n今的,最大流问题(若把一个网络图看成是一个公路网,最大流问题就是通过这个公路网的最大运输量)的卡扎诺夫算法是0(n3)的,这些都是著名的多项式时间算法。第三类是有些问题虽能写出其算法,但被认为不可能存在多项式时间算法,这样的问题有整数规划(要求答案是整数的纯线性规划),为旅行推销员(货郎担)问题:一个推销员(货郎)要到n个村庄去推销商品,最后回到原出发点,求最短巡回路程。但在70年代后期形成了一个新的理论,把上述两个问题及其它许多问题归成一类,称为NP一完备问题。直观地讲,一个NP一完备问题是一个与任一合理的问题同样困难的计算问题,具有下述性质:1任何一个NP一完备问题都不能用任何已知的多项式算法求解;o若任何一个NP一完备问题有多项式算法,则一切NP一完备问题都有多项式算法。根据这两个事实,很多人猜想任何NP一完备问题都没有多项式算法,但无人能证明它。事实上,现在人们相信,不发展全新的数学技术就证明不了这个猜想。NP一完备问题的概念的实际意义就在于人们普遍相信,难计算是这样一些问题的固有性质。因此它们不能用有效的方法求解,所以通常对这一类问题的研究或者是满足于寻找一些求近似解的方法,或者是考虑这些问题的特殊情况。因为NP一完备问题的某些特殊情况可能是多项式时间的算法。当然,NP一完备问题没有多项式时间算法目前还只是一个猜想。无论证明或推翻这个猜想,都将成为数学和计算机科学领域的一件大事。人们正翘首以待。——赵子都《算法分析和计算复杂性理论》自动化博览由于哥德尔、图灵等一批数理学家的工作,终于使人们认识到,并非所有的数学问题都是可以通过计算来解决的,如1936年图灵指出,无法找到一个计算程序,能在任意一种输入下判定该程序是否会停止(这就是著名的停机定理),再如19。。年希尔伯特提出的丢番图方程是否有整数解的问题也是不可解的。真正可以通过计算来解决的问题只是那些最终可以化归为一般递归函数的问题。这里所谓可解或不可解是指一定的间题具有或不具有相应的计算方法即算法。算法就是求解某类问题的通用法则或方法，它能够在有限步骤内一步一步地完成对问题的求解。人们也常常把它看成是用某种精确的计算机语言写成的计算机程序。另外,这里说的’“问题”也是特指某一类问题,而不是某一个具体的问题,意即不是指2x2+3x+4二5这么一个具体的一元二次方程,而是指ax,+bx+c=d这种一般或一类问题。如果一个算法可以应用于某类问题M的任何实例m,并且能保证得到实例m的解,那么就称该算法解决了问题M,或称问题M是可解的,否则,问题M是不可解的。停机问题、丢番图问题之所以不可解就是因为它们不存在相应的算法,而一元二次方程可解也就在于它存在相应的算法。然而数学问题并非就是如此简单地被分为可解的即有算法的与不可解的即无算法的两类,对于许多原则上具有算法的问题,由于计算时间长到人们无法接受(如数个世纪),实际上便也成了无法解决的问题。我们说这些问题具有算法,在原则上可解,那是以计算机的存储量为无限和计算时间为无限作为假定前提的。可是现实中J计算机其存储量和计算时间无不都是有限的,囚此原则二_可i{算的问题并不一定是现实可计算的问题,然而对于人类有意义的往往是现实可计算的问题。于是这就出现了一个算法的有效性问题或计算的复杂性问题。根据计算所需要的存储量和执行算法所需要的时间不同,计算或算法的复杂性又分为空间复杂性和时间复杂性。本文所述的计算复杂性在未具体说明的情况下均是指时间复杂性。时间复杂性反映了问题计算所需的时间耗费,一般是用计算的运算次数来衡量,具体说是用一个受制于问题“规模”—所需输入的数据总量或输入长度—的时间复杂性函数表示。为了使问题的计算复杂性的衡量不因计算工具的不同而异,人们统一采用了图灵机乍为标准计算模型。目前公认的是,用确定型图灵机在多项式时间内能解决的问题,或者说解决某问题的时间复杂性函数为O(P(n))(n为问题的规模,p为n的某个多项式函数),则称该问题为p类问题。如果一个问题的计算复杂性大到不能用多项式时间函数来表征时,就称它具有指数复杂性。指数增长的时间复杂性要比多项式时间复杂性大得多。——郝宁乡《计算复杂性理论及其哲学研究》自然辩证法研究第十一卷第三期综观国外提出的复杂性概念,其中绝大多数是建立在科尔莫哥洛夫(Kolmogorov)复杂性概念基础上的,与是否能够构造一个对象的算法,以及其算法的计算量的大小有关。这种类型的复杂性概念描述即计算型复杂性。科尔莫哥洛夫复杂性问题的研究主要起源于对可计算理论及其算法的研究。从20世纪30年代开始,数学家提出这样一个重要的问题:所有问题是否都有求解的算法?许多数学家首先开始寻求对自然数论域里的数论函数的可计算研究,提出了几种可计算函数(如原始递归函数、部分递归函数、递归集、递归可枚举集、可判定性和半可判定性)定义。例如,哥德尔(K.G�del)、赫博兰德(J.Herbrand)和克莱因(S.C.Kleene)1936年定义了递归函数;丘奇(A.Church)1935年提出了�转换演算;图灵(A.Turing)1936年提出了图灵机理论(它是计算机科学中可计算性理论或计算复杂性理论的基础);迈克布(A.A.Mapkob)1951年定义了正规算法。丘奇图灵论题的证明表明,存在一种通用的计算或算法复杂性定义。在计算机科学里,算法是计算机解题方法的精确描述。算法就是计算机解题的程序。20世纪40年代至60年代,数学家研究了算法的特征,给出了算法的基本规则(有穷性、确定性、能可行性等),最终导致了科尔莫哥洛夫、蔡廷和索尔莫哥洛夫各自独立发现的算法复杂性概念(以后被统称为科尔莫哥洛夫复杂性)的建立。——《复杂性概念研究及其意义》吴彤中国人民大学学报2004年第五期虽然计算复杂性理论是在可计算性理论的基础上发展起来的,但是运筹学的催生作用却无法忽视.当Edmond。在1965年提出多项式时间算法的概念时,是以组合优化理论为出发点的.组合优化是应用广泛的运筹学的重要分支之一它含有许多有趣而有价值的间题,……今天,当我们谈论NP完全性时,若没有特别指明哪种归约,均指Karp归约.Karp的工作犹如一声惊雷,震醒了许多面对桌上的难题而一筹莫展的人们.他们纷纷证明这些问题也是NP完全的.到现在为止,已证明的NP完全问题达二千多个了.这些问题夙旅行售货员问题是一样难的,换句话说,要么大家都有多项式时间算法,要