计算复杂度理论

来自计算思维百科
跳转至: 导航搜索

计算复杂性理论(Computational Complexity Theory)是用数学方法研究各类问题的计算复杂性的学科。

基本概念

计算复杂性理论(Computational Complexity Theory)是用数学方法研究各类问题的计算复杂性的学科。它研究各种可计算问题在计算过程中资源(如时间、空间等)的耗费情况,以及在不同计算模型下,使用不同类型资源和不同数量的资源时,各类问题复杂性的本质特性和相互关系。计算复杂性理论是理论计算机科学的分支学科,它是算法分析的理论基础。

发展

1964年,美国的J.Hartmanis和R.E.Stearns在普林斯顿举行的第5届开关电路理论和逻辑设计学术年会上发表了论文Computational complexity of recursive sequences(递归序列的计算复杂性),文中首次使用了“计算复杂性”这一术语,由此开辟了计算科学中的新领域。为此他俩获得了1993年度图灵奖。

美国麻省理工学院M.Blum完成的博士论文是:A machine independent theory of the complexity of recursive functions(递归函数复杂性的机器独立理论),该论文的详细摘要在1967年公开发表。Blum论文不但提出了有关计算复杂性的一些公理,而且在对复杂性类的归纳上也具有更高的抽象度。此外,Blum还致力于将这一理论应用到对计算机系统的安全性有着重要意义的密码学,以及软件工程中的程序正确性验证方面,都取得了令人瞩目的成就。Blum是计算复杂性理论的奠基人之一,为此他获得了1995年度图灵奖。

此后,许多研究人员对计算复杂性理论做出了不同程度的贡献。其重要的内容包括:对随机算法的去随机化的研究,对近似算法的不可近似性的研究,以及交互式证明系统理论和零知识证明等。特别是复杂性理论对近代密码学的影响非常显著,而最近复杂性理论的研究人员又进入了博弈论领域,并创立了“算法博弈论”这一分支学科。

算法复杂性

算法复杂性是算法效率的度量,它是评价算法优劣的重要依据。一个算法复杂性的高低体现在运行该算法时所需要的资源,所需资源越多,算法复杂性越高;反之,所需资源越低,则算法复杂性越低。计算机的资源,主要是指运行时间和存储空间。因而,算法复杂性有时间复杂性和空间复杂性之分。

对于任意给定的问题,设计复杂性尽可能低的算法是人们在设计算法时追求的一个重要目标。另一方面,当给定的问题已有多种算法时,选择其中复杂性最低者,是在选用算法时应遵循的一个重要准则。因此,算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。

计算复杂性

算法复杂性是针对特定算法而言的,而计算复杂性则是针对特定问题而言的,后者反映的是问题的固有难度。计算复杂性等于最佳的算法复杂性,它在计算科学中既有理论意义,又有实用价值。

计算复杂性是利用计算机求解问题的难易程度。其度量标准:一是计算所需的步数或指令条数(即时间复杂度),二是计算所需的存储空间大小(即空间复杂度)。当然没有必要就一个一个具体问题去研究它的计算复杂性,而是依据问题的难度去研究各种计算问题之间的联系。

一个问题的规模是指这个问题的大小。一个算法的计算复杂性直接决定了这个算法可以用到多大规模的问题上。假设有求解同一个问题的两个算法,第一个算法的计算复杂性是n3,第二个算法的计算复杂性是3n。用每秒百万次的计算机来计算,当n=60时,第一个算法只要用时0.2秒,而第二个算法就要用时4×1028秒,也就是1015年,相当于10亿台每秒百万次的计算机计算一百万年。

考察上面提到的两个算法复杂性,前者n3是一个多项式函数,后者3n是一个指数函数。当n很大时,这两个算法的效率差别是很大的。因此,一个问题如果没有多项式时间计算复杂性的算法,这一问题就被称为是难解型问题。但是,要断定一个问题是否是难解型问题也是很困难的。一个问题即使长期没有找到多项式时间计算复杂性算法,也不能保证明天就一定找不到,更不能据此证明这个问题不存在多项式时间计算复杂性算法。