上海市智能信息处理重点实验室 Shanghai Key Laboratory of Intelligent Information Processing

复旦大学 | 计算机科学与工程系
简介 | 宗旨 | 研究内容 | 管理架构
知识科学 | 文本处理 | 算法分析与设计 | 并行编译 | 自然语言理解、语义网 | 认知科学 | 网格计算 | 量子计算 | 图像识别、机器学习、人工生命 | 生物信息学
学术委员会 | 行政领导 | 室务委员会 | 科研队伍
学术会议 | 学术报告 | 学术交流 | 最新成果
开放课题管理办法 | 开放课题申请指南 | 开放课题申请表 | 开放课题年度报告 | 课题资助列表
基于Web的语言驱动足球赛 | 皮影数字动画 | 分形城 | 基因数据仓库
small logo

计算复杂性理论简介

洪加威

理论计算机科学的分支学科,使用数学方法对计算中所需的各种资源的耗 费作定量的分析,并研究各类问题之间在计算复杂程度上的相互关系和基本性质 ,是算法分析的理论基础。为了计算一类问题,总要耗费一定的时间以及存储空间 等资源。资源耗费的多少决定于被计算问题的大小,是问题大小的函数,称为问题 对该资源需求的复杂度。对复杂度函数增长的阶作分析,探讨它们对于不同的计 算模型在一定意义下的无关性,根据复杂度的阶对被计算的问题分类,研究各种不 同资源耗费之间的关系,对一些基本问题的资源耗费情况的上、下界作估计等,构 成计算复杂性理论的主要研究内容。

  数理逻辑和数学本身的发展,在20世纪30年代建立了 可计算性理 论 。40年代以后,随着计算机科学技术的发展,人们不仅需要研究理 论上的、原则上的可计算性,还要研究现实的可计算性,即研究计算一个问题类需 要多少时间,多少存储空间;研究哪些问题是现实可计算的,哪些问题虽然原则上 可计算,但由于计算的量太大而实际上无法计算等。这就使得计算复杂性理论作 为理论计算机科学的一个分支而发展起来。

计算模型  计算模型 为了对计算作深入的研究,需要定义一些抽象的机器。30 年代所定义的简单 图灵机 、递归函数等都是计算的模型 。但当时都只考虑到理论上的可计算性而没有考虑计算的复杂性。因此,为了度 量计算的复杂性,70年代前后又提出 多带图灵机模型 随机存取机器模型 等串行计算模型和 向量机器模型 等并行计算模型。

资源  资源 资源的确切定义决定于计算的模型。例如,对于多带的图灵机 ,就有串行时间、空间、巡回等资源(见 公理复杂性理论 )。一般说来,各种模型的主要资源有并行时间、空间和串行时间三种。

并行时间和巡回  并行时间一般指并行计算模型计算时所需步数,例如向量机的自始至 终执行指令的总条数。但对串行模型也可以定义一种称为巡回的资源。可以证明 它相当于并行时间。对于多带图灵机,它是工作带头部改变方向的次数。 一般地 说,巡回是周相的总数,而周相则是串行模型工作中的一个阶段, 在此阶段中被计 算出来而记录在工作空间上的信息,在此阶段内不再被读到。

空间  在计算过程中需要记录下来以备后用的最大中间信息量。对于多带 图灵机,是计算过程中用过的工作带上的方格数。

串行时间   计算过程中原始运算的总量。因此,对于串行模型而言,它代表计算 自始至终的总步数。对于并行模型而言,每一步可以同时作许多个原始的运算,自 始至终各步的原始运算数目的总和就是串行时间。

最坏情铝复杂度和平均情铝复杂度  最坏情铝复杂度和平均情铝复杂度 在定义任何一种资源时,例如定 义时间耗费时,时间是输入字符串w的函数,记为t(w)。对于所有长度等于n的字w , t(w)中必有最大的一个(可能是无穷大),这个值只与n有关,可以记为T(n),称为 最坏情况复杂度。如果考虑对所有长度等于n的字,取t(w)的平均值,就得到平均 复杂度。它当然不超过最坏情况复杂度。

相似性原理  相似性原理 对图灵论题的进一步研究,可断言各计算模型在计算能 力上的大致等价性。也就是说,对于同一类计算问题而言,各理想的计算模型使用 本质上同样多的并行时间、本质上同样多的空间和本质上同样多的串行时间,三 者同时成立。所谓本质上同样多是指多项式相关联。

  以多带图灵机和向量机器为例,可以证明下面的相似性定理:设n是输入字符 串的长度,它代表问题的大小。对于任何一个多带图灵机,设它的巡回为R(n),空 间为S(n),串行时间为T(n),则一定有一个向量机器来模拟它,使得存在一个多项 式p, 向量机器的并行时间R 1 (n),空间S 1 (n)和串行时间T 1 (n)满足R 1 (n)≤p(R(n) )S 1 (n)≤p(S(n))T 1 (n)≤p(T(n))在以上 结论中把多带图灵机和向量机器的位置对调一下也成立。这说明在多项式相关联 意义下,这两个模型没有本质的区别。因此,巡回是串行模型的虚拟并行时间。

计算的类型  计算的类型 这里只考虑判定问题或是非问题。机器状态转移和接受 输入的方式称为计算的类型。在普通计算中,机器状态只依赖于时间和输入,是完 全确定的。每一步都由前一步所达到的状态唯一确定。如果机器最后进入一个接 受状态,就认为机器接受了输入。这种计算称为确定型的,计算的过程可以用一条 链来表示(图1)。确定型是最简单的一种计算类型。

  但有时机器在某一时刻可以有若干种选择,进入若干不同状态,而在新的情况 下又有若干不同选择等。这时计算过程可用一棵树表示(图2)。若规定只要有一 条路从树根通向一个接受的顶点,就认为机器接受了输入字符串,这种接受方式就 叫做非确定型的(见非确定性)。此 图1 确定型计算 图2 非确定型计算 时,树高被看作是非确定计算所需的时间。

  随机型计算的定义有许多种。较弱的一种定义为:从计算树的根往下走,每到 一个岔路口就扔一枚钱币以决定去向。如果用这种方式碰到一个接受状态的概率 大于1/2,就接受输入字w。较强的一种定义为:如果输入应该被拒绝则机器一定拒 绝,如果输入应该被接受则机器接受的概率大于或等于1/2。或者说,若输入该被 拒绝,机器是不会犯错误的;否则机器犯错误的可能性不超过一半。这种算法又称 为概率算法。

   R.索罗威和V.史托拉森找到一个多项式时间的随机型素数判定算法。若被判 定的数m的确是一个素数,则算法一定会回答是素数。若m不是素数,则算法回答是 素数的可能性小于1/2。可以不断对m重复这一算法,而且每次的结果是独立的。 例如重复100次,若每次回答都是素数则可断言它是素数,只要有一次回答不是素 数则可以肯定它不是素数。这样,犯错误的可能性将小于2 -100 。由于尚未找到确定型多项式时间素数判定算法,这类概率算法就具有 很重要的意义。最早的这样一个算法由E.R.伯勒嵌普给出。他找到一个多项式时 间的概率算法,去分解p个元素的域GF(p)上的一个多项式。

  计算理论中有重要意义的计算类型还有交错型等。

  相似性原理和相似性定理不仅对确定型计算成立,而且对非确定型、交错型 、随机型等各种计算类型都是成立的。

复杂性类  复杂性类 根据识别时资源耗费的复杂程度而对形式语言所作的分类 。在多项式时间内用确定型机器可识别的语言可归入一类,记为P。把那些用非确 定型机器在多项式的串行时间内可识别的语言归入一类,记为NP(见NP 完全性 )。在这种条件下无需说明采用什么计算模型,因为根据相似 性原理,不论采用何种模型,P和NP的意义是不变的。

   N.皮彭格提出P的一个重要子类称为NC,它由所有同时可在多项式的空间和对 数多项式的并行时间内可计算的函数组成。如果说P代表现实可计算的问题,那么 NC即代表其中用多项式处理机在对数多项式时间内计算的问题。整数的加减乘除 运算、整序、图联通性、矩阵的乘法、除法、行列式、多项式的最大公因子、上 下文无关语言识别、找图的最小张开树等问题都属于NC。

  与之对偶的另一个子类由所有同时可在多项式的并行时间和对数多项式的空 间内计算的函数所组成,称为SC。

  在确定型多项式空间中可判定的语言类记为PSPACE。就已有的计算模型而言 ,在确定型多项式并行时间中可判定的语言类恰为PSPACE。

  当然,还可以考虑概率型的机器在对数多项式并行时间和多项式空间中可识 别的语言类等。根据相似性原理,这些类的定义都是独立于计算模型的。

归约和完全性  归约和完全性 研究复杂性类和其间关系的方法。在数学中,常常把 一类问题的计算归结为另一类问题的计算。例如,利用公式 〖FK(W2〗〖WTBX〗〖JZ〗x〖DK〗·y=〖SX(〗1〖〗2〖SX)〗[(x+y )2-x2-y2]〖FK)〗〖WTBX〗 可把乘法归约为平方、加减法和用2除。如果平方、加减法和用2除 能很快算出来,乘法也就可以很快地算出来。

  设有两个语言L 1 、L 2 和一个简单易行 的变换T,如果一个字X属于L 1 ,当且仅当变换以后的字T(x)属 于L 2 ,那麽就说变换T把L 1 归约成L 2 。因为,若要判定某个字X是否属于L 1 ,只 要用T变换一下,然后去判断T(x)是否属于L 2 就行了。为了使 得归约是有实际意义的,就要求T是一个容易实现的变换。例如,可在对数空间中 实现。这时就说L 1 在对数空间中归约为L 2 。

  设C是一个复杂性类, L是任一语言。 如果C中任何语言都可以在对数空间中 归约为L,就说C可在对数空间中归约为L。 或者说, L属于C难。其直观意义为: 若L可以容易地计算出来,则C中任何问题均可以容易地计算出来。 反之, 若C中 有难于识别的问题, 则L的识别肯定不会更容易 (故称为C难)。 进一步说, 如果 L属于C难, 而且本身也属于C,就说L在C中是完全的。意思是:C中任何语言可以很 快识别, 当且仅当人可以很快识别。

  归约和完全性是复杂性理论中重要的研究方法。第一个NP完全性问题由S.A .库克在1971年提出,R.卡尔普等人解决了一系列基本的NP完全性问题。

复杂度的上界和下界  复杂度的上界和下界 用以估计问题所需某资源的复杂程度的界限函 数。如果找到解某问题的算法,其资源的复杂度为u(n),则u(n)是问题本身复杂度 的一个上界。如果对任何算法,其复杂度都必需大于l(n),则l(n)是问题复杂度的 一个下界。

  对各类具体问题的复杂度的上、下界的研究,一般说来属于算法分析的范围 。但有时也把某些基本问题的上、下界的研究归入复杂性理论。

   n维的快速傅里叶变换需要O(n log n)次算术运算;n位的乘法在多带图灵机 上需时O(n log n log log n);n阶矩阵乘法只需要4.7n 2.81 次算术运算,判定一个n位数是否为素数需时O(n clogloglog n );在出度限定情形下的图同构的判定,存在多项式时间算法。

  下界的结果多借助于对角线方法得出,最典型的是关于复杂性谱系的一系列 结果。带有平方的正规表达式的等价问题的判定需要指数的空间。例如,不难证 明,为了把n个数排序,比较的次数至少正比于n log n。又如n个点的多项式的插 值问题,若只许用算术运算,则至少需要 nlogn次乘法。关于两个资源乘积的下界 ,为了识别n位的完全平方数,在一个离线的图灵机上,时间和空间的乘积至少正比 于n 2 。为了对n个大小从1到n 2 之间的数排 序,时间和空间的乘积至少正比于n 2 /log n。为了识别任何非 正规的语言,多带图灵机的工作空间和工作带巡回数的乘积的阶不能小于n。

  从发展趋势来看, 计算复杂性理论将深入到各个数学分支中去。计算机科 学的发展,特别是 新一代计算机系统 人工智 能 的研究,又会给计算复杂性理论提出许多新的课题。计算复杂性理 论、描述复杂性理论、信息论、数理逻辑等学科将有可能更紧密结合,得到有关 信息加工或信息活动的一些深刻结论。

参考书目 A.V.Aho,J.E.Hopcroft & J .D.Ullman,The Design and Analysis of Computer Algorithms,Addison-Wesl ey,Reading,Mass.,1974. J.E.Hopcroft& J.D.Ullman,Introduction to Autom ata Theory, Languages and Computation,Addison-Wesley,Reading, Mass., 1979.

Copyright © 2002-2006 上海市智能信息处理重点实验室 版权所有

地址:上海邯郸路220号 电话:+8621-65654549 传真:+8621-65654253 Email: Webmaster