计算复杂性理论

《计算复杂性理论》由会员分享，可在线阅读，更多相关《计算复杂性理论（13页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

5、论的研究者又进入了 博弈论领域，并创立了“算法博弈论”（algorithmic game theory）这一分支。该领域重要的研究者有（不完全列表）：史提芬古克姚期智 （Andrew Chi-Chih Yao）Allan BorodinManuel BlumJuris HartmanisRichard KarpLeonid LevinAlexander RazborovMichel SipserAvi WigdersonWalter SavitchRichard StearnsLance FortnowV. ArvindLazlo Babai编辑 基本概念和工具基本概念和工具编辑 计算模型与计

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

7、使得我们可以仅仅关注图灵机而忽略其它的计算模型。编辑 判定性问题和可计算性判定性问题和可计算性主条目：判定性问题我们考虑对一个算法问题，什么样的回答是我们所需要的。比如搜索问题：给 定数组 A，和一个数 s，我们要问 s 在不在 A 中（判定性问题，decision problem）。而进一步的，s 如果在 A 中的话，s 的位置是什么（搜索型问题， search problem）。再比如完美匹配问题（perfect matching）：给定一个二 分图 G=(V,E)，我们问是不是存在边集 E，使得二分图中每个结点恰好属于该边 集的一条边（判定型问题）。而进一步的，E 存在的话，E 具体是什

8、么（搜索型 问题）。自然的，我们会发现对于一般的算法问题 A，我们都可以这样来问：首先，解 是不是存在的？其次，如果解存在，这个解具体是什么？这就是 A 的判定型问 题和 A 的搜索型问题（又称函数型问题）区分来源的直观解释。对判定型问题 的回答只需是“是”或“否”，而对搜索型问题，需要返回解的具体形式或者 “解不存在”。所以一个对 A 的搜索型问题的算法自然的也是对 A 的判定型问 题的算法。反之，给定了一个 A 的判定型问题的算法，是否存在 A 的搜索型问 题的算法，在可计算性理论和计算复杂性理论中有着不同的回答，这也是理解 计算复杂性理论与它的前身可计算性理论不同的一个基本的观察。在可计

9、算性理论中，可以说明，判定型问题和搜索型问题在可计算性的意义下 是等价的（见 Decision problem）。而在计算复杂性中，Khuller 和 Vazirani 在 1990 年代证明了在 PNP 的假设下，平面图 4-着色问题的判定型问题是在 P 中的，而寻找其字典序第一的着色是 NP 难的。1所以在可计算性理论中，只关注判定型问题是合理的。在计算复杂性理论中， 虽然一些基本的复杂性类（如 P，NP 和 PSPACE），以及一些基本的问题（P 和 NP 关系问题等）是用判定型问题来定义的，但函数型问题复杂性类也被定义 （如 FP，FNP 等），而且一些特别的函数型问题复杂性类，如 T

10、FNP，也正在逐 渐受到关注。编辑 算法分析算法分析上面提到计算复杂性理论的研究对象是执行一项计算任务所用的资源，特别的， 时间和空间是最重要的两项资源。我们用时间作例子来讨论算法分析的一些基础知识。如果将输入的长度（设为 n）作为变量，而我们关注的是算法运行时间关于 n 的函数关系 T(n)。因为一 个算法在不同的计算模型上实现时 T(n)可能会有常数因子的差别（参见可计算 性理论），我们使用大 O 表达式来表示 T(n)，这使得我们可以忽略在不同计算 模型上实现的常数因子。以搜索这个计算任务为例。在搜索问题中，给定了一个具体的数 s，和长度为 n 的数组 A（数组中数的位置用 1 到 n

11、作标记），任务是当 s 在 A 中时，找到 s 的位置，而 s 不在 A 中时，需要报告“未找到“。这时输入的长度即为 n+1。下 面的过程即是一个最简单的算法：我们依次扫过 A 中的每个数，并与 s 进行比 较，如果相等即返回当前的位置，如果扫遍所有的数而算法仍未停止，则返回“ 未找到“。如果我们假设 s 在 A 中每个位置都是等可能的，那么算法在找到 s 的条件下需 要 1/n (1+2+.+n)=n(n+1)/2n=(n+1)/2 的时间。如果 s 不在 A 中，那么需要 (n+1)的时间。由大 O 表达式的知识我们知道算法所需的时间即为 O(n)。而如果我们进一步假设 A 是已排序的，

12、那么我们有二分查找算法，使得算法的 运行时间是 O(logn)。可以看出执行一项计算任务，不同的算法在运行时间上 是有很大差异的。编辑 复杂性类复杂性类将计算问题按照在不同计算模型下所需资源的不同予以分类，从而得到一个对 算法问题“难度”的类别，就是复杂性理论中复杂性类概念的来源。例如一个 问题如果在确定性图灵机上所需时间不会超过一个确定的多项式（以输入的长 度为多项式的不定元），那么我们称这类问题的集合为 P（polynomial time Turing machine）。而将前述定义中的“确定性图灵机”改为“不确定性图灵 机”，那么所得到的问题集合为 NP（non-deteministic

13、 polynomial time Turing machine）。类似的，设 n 为输入的长度，那我们可以定义“在确定性 图灵机上所需空间不超 O(logn）的算法问题的集合”（即为 L），“存在深度 为 O(logn)，输入的度（fan-in）为 O(1)的电路族（circuit family）的算法 问题的集合”（即为 NC1）等等复杂性类。定义复杂性类问题的目的是为了将所有的算法问题进行分类，以确定当前算法 的难度，和可能的前进方向。这是复杂性理论的一个主线之一：对算法问题进 行抽象和分类。例如透过大 O 表达式，我们可以对忽略因计算模型不同而引入 的常数因子。而第二个重要的理论假设，就

14、是将多项式时间作为有效算法的标志（与之对应的是指数时间）。这样，复杂性类使得我们可以忽略多项式阶的 不同而专注于多项式时间和指数时间的差别。（对多项式时间作为有效算法的 标志这一点是有一定争议的，比如，如果算法的运行时间 n10，那它也可以看作 是缓慢的，见理论与实践。）在本文的其余章节，“有效算法”等价于“多项 式算法”编辑 归约归约归约（reduction）是将不同算法问题建立联系的主要的技术手段，并且在某种 程度上，定义了算法问题的相对难度。简单来说，假设我们有算法任务 A 和 B，如果我们想说“A 比 B 简单”（记为 AB），它应该是什么意思呢？从归约 的观点来看，就是说如果我们有了

15、 B 的有效算法 M，那么我们有一个有效算法 N，它可以引用 M，最终它要解决 A 问题。我们以点集覆盖问题（vertex cover）和独立集问题（independent set）为例 来进行说明。这两个问题都是图论中的问题。假设给定了无向图 G=(V, E)，和 一个自然数 k，点集覆盖问题是要找到 V 的子集 S，使得对eE，有 s S， 使得 s e，且|S|k；而独立集问题也是要找 V 的子集 S，要求是s1, s2S，(s1, s2) E，且|S|k。一个简单的观察即是：对 G=(V, E)，一个 SV 是覆盖点集，当且仅当 S 在 G 的补图中是独立点集（而且保持集合大小）。利用

16、这个观察，假设我们有了解 决覆盖点集问题的算法 M，我们设计解决独立点集的算法 N 如下：算法 N。o输入：给定无向图 G=(V, E)，自然数 k；o输出：一个大小 k 的独立点集（如果存在，否则返回“不存在” ）；o已知：算法 M，输入为(无向图 G, 自然数 k)，输出大小 k 的覆 盖点集，如果这样的点集存在。否则返回“不存在”；算法步骤：1. 对 G，产生 G 的补图 G； 2. 调用 M，输入为(G, k)； 3. 如果 M 返回“不存在”，输出不存在。如果 M 返回 SV，输出 S。可以看出若产生补图这一步是有效的，那么如果 M 有效，N 也是有效的。一般 的，如果我们有一个 B 有效的算法 M，和利用 B 作为“神谕”（oracle）的解 决 A 问题的算法 N，那么如果 N 是有效的，则我们有有效的解决 A 问题的算法 N只需将 N 中查询 B 的操作换作具体的 M 算法即可。而这一性质的基本解 释是：将多项