————————————————————— 附录 —————————————————————

http://210.45.210.9:918/web/index.htm  

  

　　复杂性理论和算法分析 　可计算性理论在逻辑上的进一步发展，就是计算复杂性理论。著名的图灵-丘奇论题说，凡是合理的计算模型都是等价的，即一个模型能计算的，在别的模型下也能计算，否则都不可计算。但是对于一个问题类而言，只知道能不能计算是很不够的，更有实际意义的是要知道计算需要多少时间，多大的内存等等。由此产生了计算复杂性理论和算法分析。
　　计算所需的时间、存储大小等等都算为资源。严格地讲，每一种资源的定义都依赖于一个计算模型。各种计算模型的资源的定义虽不一样，但是主要的有三种。
　　①  串行时间　简称时间， 它是计算过程中的总运算量。也即把计算分成一些原始的步骤，完成这些步骤所需的总时间。
　　②  空间  它是为了保存计算的中间结果所需地盘的大小。例如在计算时用一块黑板来打草稿，假定每一单位黑板面积可以写一个符号，且可以擦掉重写，空间就相当于打草稿所需的黑板面积。
　　③  并行时间  即并行计算所需的时间。也即多人或多机协同计算，解决一个问题所需要的时间。
　　复杂性总是对于一个特定的问题类来讨论的，其中包括无穷多个个别问题，有大有小。例如对矩阵乘法这一问题类而言，相对地说100阶矩阵相乘就是一个较大的问题，而二阶矩阵相乘则是个较小的问题。所以可以把阶n作为衡量问题大小的尺度。但是最一般地，是把输入的总长度n作为问题大小的尺度。因此，当给定一个算法以后，计算一个大小为n的问题所需的时间、空间等就可以表为 n的函数。这个函数就叫做该算法的时间或空间的复杂性之度量，或称为复杂度。严格地讲，它是这个特定的问题类在某一特定计算模型中的某一算法下的复杂度。当要解决的问题越来越大时，时间、空间等资源的耗费将以什么样的速率增长，也即当n趋于无穷时这个函数增长的阶是什么？这就是复杂性理论所关心的问题。
　　在计算同一个问题类时，算法有好坏之别。例如要判定一个具有n个顶点的无向图中有没有回路，早期的算法所需的空间复杂度为S(n)=O(log²n)，但是后来设计了更精细的算法，它的空间复杂度只有O（logn）。这说明O（log²n）只是早期算法的空间复杂度，而并非这个问题本身的内在复杂度。或者说O（log²n）只是回路问题空间复杂度的一个上界，而O（logn）则是一个新的更好的上界。对于回路问题，任何算法都至少需要正比于logn的工作空间。这就是说，对于任何算法，空间复杂度S(n)=Ω(logn)。因此可以认为Ω(logn)是回路问题空间复杂度的一个下界。问题内在的复杂度介于上界和下界之间。在这个例子中，二者重合了。因此可以说回路问题的空间复杂度正比于logn，记为S(n)=嘷(logn)。
　　又如两个n位二进整数的乘法在多带图灵机模型下，一般的算法需时O(n²)。但改进的算法可以达到O(n^1.5)。现在最好的算法可以达到O(nlognloglogn)。如果采用存储可修改机器做模型，则可以达到O(n)。可以看出一个问题的内在计算复杂性还因计算模型的不同而有高低。
　　较为重要而且具有特色的计算模型主要有多带图灵机器，多带多维多头图灵机器，硬件可修改机器（HMM），随机存取机器(RAM)，并行随机存取机器(PRAM)，向量机器，VLSI，等等。然而没有一个适合一切问题的统一的模型。这样，复杂性的问题有没有一个相对统一的标准呢？相似性原理解答了这一问题。按此原理，计算一个问题类使用的并行时间、空间和串行时间的复杂程度在所有理想的计算模型中都没有本质的差异。用数学语言来说，各种模型不仅可以相互模拟而且模拟者所需的并行时间、空间和串行时间都分别不超过被模拟者需用的并行时间、空间和串行时间的一个多项式。所以在只差一个多项式的范围内，复杂性还是有其客观依据而是不依赖于模型的。对于上面提到的各种模型，以及各种计算类型，相似性原理已被证明是正确的。
　　对于串行计算模型都可以定义一个虚拟的并行时间，叫做巡回。所谓巡回，是指计算过程中的周相数。而一个周相则是计算过程中的一个阶段，在此阶段中新计算出来记在工作空间上的信息不准在同一阶段内被读到。例如，对于多带图灵机器而言，一个周相就是工作带头不改变方向的一段时间。所以巡回相当于工作带头改变方向的总次数。因此可以说，一个问题类有快速的并行算法当且仅当它有一个具有小的巡回数(虚拟并行时间)的串行算法。另外并行时间和空间之间具有某些对称的性质。例如可以证明，它们之间是多项式相关联的。所以说，一个问题类有一个快速并行时间算法当且仅当它有一个高度节省内存的算法。
　　既然在多项式关联意义下复杂性不依赖于模型，就可以用P代表所有具有多项式时间算法的问题类;用NP代表所有具有非确定多项式时间算法的问题类；用NC代表所有能同时在对数多项式并行时间和多项式空间解决的问题类；等等。
　　一般认为，P中的问题才具有现实的可计算性，但有许多实际问题属于NP，却未能找到一个确定型多项式时间算法。所以许多人猜想PNP。1971年库克在NP中找到一个问题类，叫做布尔合取范式的可满足性问题(SAT)。证明了NP中任何一个问题类的计算均可归约为SAT的计算。因此，称SAT为一个NP完全性问题（见组合最优化），NP=P当且仅当对SAT存在一个确定型多项式时间的算法。以后C.卡普等人又把SAT归约为许多其他的组合问题，得出了许多其他的NP完全性问题。目前NP完全性问题几乎涉及到一切数学的分支，形成了一个专门的理论。但是NP是否等于P的问题尚未解决。有人猜想它是独立于现有的数学公理系统的。完全性的研究不限于NP完全性。对于各个复杂性类，都有完全性问题。
　　在复杂性基本理论的基础上，对各类具体数学问题的复杂性研究构成了算法分析的主要内容，60年代以来取得了长足的进展。例如n维的快速傅里叶变换和n次多项式的乘法， 只需要O(n logn)次算术运算；n位的数乘在多带图灵机上只需O（nlognloglogn）的时间;判定一个n位数是否为素数需时O()；在出度限定情况下，图同构的判定问题存在多项式时间的算法；判定整系数线性规划问题是否存在有理解，存在多项式时间算法；n阶矩阵乘法只需4.7n^2.8次算术运算;后来又改进为O(n)，还证明了，这个阶可以无穷地改进下去，等等。
　　对比于上界的情况，下界的研究却碰到了许多困难，尤其是对一些具有实际意义的问题。例如对任何一个NP完全性问题，猜想至少需要指数的时间，但多年来连一个非线性的下界都证不出来。
　　除了计算的复杂性，还有描述的复杂性，这是Α.Η.柯尔莫哥洛夫和察廷提出来的。 一个01串w 的信息量I(w)被定义为输出w 的最小程序的长度。因为各个模型可以互相模拟，故以上的定义在只差一个常数值的意义下，是不依赖于模型的。因为任何一个数学公理系统所包含的信息量是有限的，因而在这个系统中不可能证出I(w)≥с形的定理，这里с是只依赖于公理系统的一个常数。但容易知道，除了有限多个w 以外，所有的w 都满足I(w)≥с（却无一能被证明）。这一结果简化和加强了哥德尔不完备性定理。

洪加威