3 计算复杂性理论

《3 计算复杂性理论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算复杂性理论（Computationalcomplexitytheory）是计算理论的一部分，研究计算问题时所需的资源，比如时间和空间，以及如何尽可能的节省这些资源。目录[隐藏]·1简介·2历史·3基本概念和工具o3.1计算模型与计算资源o3.2判定性问题和可计算性o3.3算法分析o3.4复杂性类o3.5归约·4NP与P关系问题及相关理论o4.1NP和P的定义o4.2NP与P关系问题o4.3NP完备理论o4.4电路复杂性o4.5其它NP与P关系问题相关的理论·5理论与实践·6参考·7外部链接[编辑]简介计算复杂性理论所研究的资源中最常见的是时间（

2、要通过多少步才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此

3、问题所需要的工作带格子数总和称为空间。复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源。而复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法理论专注于设计有效的算法，而复杂性理论专注于理解为什么对于某类问题，不存在有效的算法。[编辑]历史在20世纪50年代，Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来，被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns的1960年代的论文Onthecomputationalcomplexit

4、yofalgorithms。在这篇论文中，作者引入了时间复杂性类TIME(f(n))的概念，并利用对角线法证明了时间层级定理（TimeHierarchyTheorem）。在此之后，许多研究者对复杂性理论作出了贡献。期间重要的发现包括：对随机算法的去随机化（derandomization）的研究，对近似算法的不可近似性（hardnessofapproximation）的研究，以及交互式证明系统（Interactiveproofsystem）理论和零知识证明（Zero-knowledgeproof）等。特别的复杂性理论对近代密码学的影响非常显著，而最近

5、，复杂性理论的研究者又进入了博弈论领域，并创立了“算法博弈论”（algorithmicgametheory）这一分支。该领域重要的研究者有（不完全列表）：·史提芬·古克·姚期智（AndrewChi-ChihYao）·AllanBorodin·ManuelBlum·JurisHartmanis·RichardKarp·LeonidLevin·AlexanderRazborov·MichelSipser·AviWigderson·WalterSavitch·RichardStearns·LanceFortnow·V.Arvind·LazloBabai[

6、编辑]基本概念和工具[编辑]计算模型与计算资源计算复杂性理论的研究对象是算法在执行时所需的计算资源，而为了讨论这一点，我们必须假设算法是在某个计算模型上运行的。常讨论的计算模型包括图灵机（Turingmachine）和电路（circuit），它们分别是一致性（uniform）和非一致性（non-uniform）计算模型的代表。而计算资源与计算模型是相关的，如对图灵机我们一般讨论的是时间、空间和随机源，而对电路我们一般讨论电路的大小。由邱奇-图灵论题（Church-Turingthesis），所有的一致的计算模型与图灵机在多项式时间意义下是等价的。而

7、由于我们一般将多项式时间作为有效算法的标志，该论题使得我们可以仅仅关注图灵机而忽略其它的计算模型。[编辑]判定性问题和可计算性主条目：判定性问题我们考虑对一个算法问题，什么样的回答是我们所需要的。比如搜索问题：给定数组A，和一个数s，我们要问s在不在A中（判定性问题，decisionproblem）。而进一步的，s如果在A中的话，s的位置是什么（搜索型问题，searchproblem）。再比如完美匹配问题（perfectmatching）：给定一个二分图G=(V,E)，我们问是不是存在边集E，使得二分图中每个结点恰好属于该边集的一条边（判定型问题）

8、。而进一步的，E存在的话，E具体是什么（搜索型问题）。自然的，我们会发现对于一般的算法问题A，我们都可以这样来问：首先，解