测度和复杂性分类.doc

语言与计算理论导引 可计算函数第五部分 计算复杂性导引到现在，在我们讨论决策问题时，我们只考虑问题是否具有可解的性质。在现实生活中，用于解决问题的计算资源是有限的：可获得的时间和空间都是有限的。结果，一些可解的问题的中等规模的实例在实际中都变得很难以解决。在第5部分，我们考虑鉴别难解问题的方法，主要通过描述解决问题的一定规模的实例时，所需要的时间和内存的数量。虽然，强调的重点是运行时间，我们也给出有关空间的基本定义，并提到涉及空间的最基本的结果。在第14章，我们首先引入涉及增长率的记号和术语，这允许我们在后面章节以合理的方式讨论象“多少时间？”这样的问题。我们把这些数量问题与我们特定的计算模型相联系，然后讨论一些基本的复杂类。这也是根据问题和语言内在的复杂性对它们分类的方法。为了区分易解问题和难解问题（注意，前面我们讨论的可解问题和无解问题），正如我们将在第15章讨论的，常用的标准是在图林机上是多项式时间可解的。根据这个标准，许多问题是易解的，也有些问题是难解的。我们可以修改第12章的规约技术得到这两类问题的例子。也许更有趣的问题是根据这个标准，至今仍然无法判断的一些问题，没有人发现这些问题的多项式时间解决方法，但是也没有人能够证明不存在多项式时间解决方法。NP完全的概念就是接近这个主题的一个方法。在第15章的最后两节，我们给出可满足问题的NP完全性的cook证明和一些通过多项式时间规约被证明是NP完全的组合问题的例子。14 测度和复杂性分类14.1 函数的增长率计算问题的复杂性能够通过固定的计算模型来讨论，主要考虑为了解决这个问题，需要多少机器的资源（通常指时间和空间）。为了对两个问题内在复杂性进行有意义的比较，有必要考察一定范围内的实例的解决情况。如果我们把运行时间作为标准，比如，最常用的方法是比较两个运行时间的增长率，每个运行时间都看成是实例规模的函数。我们引入一些处理运行时间的数量的增长率的定义和记号。我们从一个比较4个简单函数的例子开始。例子14.1 我们考虑函数p1(n)=2n2p2(n)=n2+3n+7P3(n)=n3q(n)=2n表14.1显示了这4个函数对应部分变量取值n的各自的函数值，这些函数值很清楚显示了每个函数的增长趋势。对于比较小的值n，p2(n)的值远远大于p1(n)，但是当n=1000时，p2(n)中低阶的项3n+7变得相对可忽略了，而p1中的因子2几乎完全决定了p1和p2之间的差别。p3是更高阶的多项式，尽管没有额外的因子和低阶项，但是它的值的增长速度比前两个函数都要快很多。更惊人的增长趋势体现在第4个指数函数q上。我们再次看到对于最前面的几个小数值没有什么特别的地方，但是对于n=10之后的数值，它就比其他3个函数值都要大了，当n=1000时，p3(n)是1百万，而q(n)则是难以想象地大了。如果表中数据的单位是纳秒（nanosecond，又译毫微秒，一秒的10亿分之一），那么p3(1000)表示1秒，而q(1000)表示超过3*10282世纪。加入表14.1表14.1展示了不同增长率的效果，p1和p2有不同的规模，主要是因为p1的因子2，但是它们的增长率是一致的。立方多项式的增长率更大一些，但是这三个多项式的增长率都远远小于指数函数。一旦我们有了能够精确描述增长率的定义，其中一个我们感兴趣的主要区别将是多项式增长率和指数增长率之间的区别。这个例子显示的许多明显的特征将体现在定义中。定义14.1 如果f,g: NN是部分函数，每个函数除了在有限个点外，其他值都是有定义的。如果存在常量C和n0，使得对于每个n=n0，f(n)和g(n)都是有定义的，且f(n)=n0，都有f(n)=Cg(n)，那么我们写f(n)=o(g(n)（或者简单地，f=o(g)）最后，如果f=O(g)且g=O(f)，则写成f=Q(g)语句f=O(g)，f=o(g)和f=Q(g)分别读着“f是g的大O”，“f是g的小o”和“f是g的大Q”。所有这些语句可以用比率f(n)/g(n)来重新描述，假设g(n)最终会大于0。说f=o(g)意味着当n趋于无穷大时，这个比率的极限为0，而f=O(g)表示这个极限是有界的，而f=Q(g)，如果两个函数都最终是非0的，则表示f/g和g/f的极限值都是有界的，即f/g的极限值介于两个固定的正数之间。如果f=O(g)不成立，则写成fO(g)，类似地，得到另外两个不成立的表示法。fO(g)意味着不存在常数C，使得对于所有的n的大值，f(n)=Cg(n)，换句话说，比率f(n)/g(n)是无界的。一个语句，比如f=O(g)，描述了两个函数的关系，它不是等式，比如写成O(f)=g是没有意义的。这个记号的定义是很清楚的，但是更精确的写法是把O(g)看成一个集合，因此fO(g)，而不是f=O(g)（为了方便，我们不加区分地使用着两种表示法）。语句f=O(g)没有传达任何有关f和g的函数值的信息，它表示长远来看（当n足够大时），也许f不再比g的某个比例大，这个比例常量可能很大，以至f的实际值可能比g要大的多，但是f的增长率并不比g大。这个术语对于非降低的函数f和g更合适，至少最终是非降低的，而大多数我们感兴趣的函数都具备这个性质。如果f=Q(g)，则说f和g具备相同的增长率，正如我们已经看到，它表示当n很大时，两个函数的值趋于一个恒定的比例。如果f=o(g)，那么f的增长率小于g，因为根据定义，当n很到时，f和g的比例比任何一个正常数都要小。注意在这里我们不关心当n要大到什么值是，上面的情况才发生。我们已经引入了一个与其他函数增长率相当（或小、或大）的函数的想法，有必要检验这些术语在语义上不会有误导，即这两个关系（大O和小o）满足绝大多数相应的数值关系的性质。根据定义很清楚，如果f=o(g)，那么f=O(g)，符合“小于”蕴涵“不大于”的语义。显然，我们还希望“大于”可以排除“不大于”的可能性，即如果f=o(g)，则gO(f)。这是容易检验的。定理14.1包含了这些关系的其他一些直观的性质。定理14.1 关系R1定义如下fR1g当且仅当f=O(g)即函数f的增长率不大于g。R1满足自反性和传递性。关系R2定义如下fR2g当且仅当f=o(g)即f的增长率小于g。R2满足传递性和反对称性（如果fR2g，则gR2f）。关系R3定义如下fR3g当且仅当f=Q(g)即f和g的增长率相当。R3是一个等价关系。证明：我们只证明R1的性质，其他两个留作练习。关系R1的自反性是显然的，根据定义，只要选择常数C=1，n0=0就可以了。下面证明它的传递性。假设f=O(g)，且g=O(h)。那么存在常数C1, n1, C2, n2使得f(n)=n1g(n)=n2令n0=max(n1,n2)，那么当n=n0，上面的两个不等式都成立，得到f(n)=C1g(n)0，那么当n足够大时，p(n)0。我们将对这类多项式感兴趣，而且如果ak=0，ak1，令q是指数函数q(n)= an其中a1，则p(n)=Q(nk)，p=o(q)证明：首先我们证明p(n)=Q(nk)。我们可以写=我们能够发现n0，使得对于任意的n=n0，下面k项的每一项, ,., , 都小于1/k。因此-11则0ak-1=n0，都小于或等于1/(2k)，因此=ak-1/2即nk=n0，有nk+1=z(n)n=an因此nk1043，而(10,000)3=1012。14.2 图林机的时间和空间复杂性我们选择的计算模型是图林机（有时为了方便，我们可能使用多个磁带或非确定的图林机），当一个图林机执行一个计算去回到一个判定问题的实例时，我们可以测量计算所需的时间（移动次数）和空间（磁带的格子数）。实例规模的最明显的测量标准是作为实例编码的输入字符串的长度，最常用的方法是考虑最坏的情况，即同样长度的输入字符串可能需要的最大时间和空间的开销。有了上面的说明，我们可以在一个普通的确定型图林机上定义时间和空间的复杂性。定义14.2（图林机的时间和空间的复杂性）令T是一个图林机，T的时间复杂性是一个定义在自然数集上的函数tT。对于一个自然数n，tT(n)是在所有长度为n的输入字符串上引发的T的最多的移动次数。如果存在一个长度为n的输入字符串，使得T无限循环，那么tT(n)无定义。空间复杂性函数sT定义如下。如果没有长度为n的输入字符串导致T使用无限多的磁带格子，sT(n)是所有长度为n的输入字符串上引发的T的使用最多的格子数目（如果T是多个磁带的图林机，“磁带格子数目”的含义是单个磁带的最大格子数）。否则如果某个长度为n的输入字符串导致T无限循环，并且这个无限循环导致无限多的磁带格子被占用，那么sT(n)无定义。例子14.2 我们考虑例子9.3的图林机T，如果14-1所示。它接受的语言是ss|sa,b*。我们推导出当n是偶数时，tT(n)的计算公式。n是奇数时的推导留作练习。分析：一个长度为2k的输入字符串处理过程分为下面三个阶段：首先，发现中点，并在这个过程中将所有的符号改成大写字母；第二，将前面一半的符号改回到小写字母，并将磁带头移回到开始位置；第三，比较前半部分和后半部分。在第一阶段，需要移动一步将磁带头放置在输入字符串的第一个字符上，因此需要2k+1步改写第一个字符并发现最右的符号，然后需要2k步改写符号并返回到最左端的小写字母上。后面的每一步将比上一步少处理两个字符，因此少4步移动。第一阶段的总的移动步数是1+(4k+1)+(4(k-1)+1)+.+(4(0)+1)=1+4+(k+1)=2k2+3k+2（此处用到了例子2.1的结果）。第二阶段需要k+1步移动。前面两个阶段需要的时间只与输入字符串的长度相关（当长度是偶数时）。在第三阶段，最大的移动步数与输入内容相关。在最坏情况下，这个过程包括k趟扫描，前半部分的字符串中的每个符号都对应一趟扫描。在每趟扫描中，需要向右的k步移动，需要向左的k+1步移动，总的步数是2k+1。因此第三阶段至多需要2k2+k步移动。这三个阶段的所有步数加起来，并加上最后移到停机状态的一步，我们得到(2k2+3k+2)+(k+1)+(2k2+k)+1=n2+5n/2+4步数。当k=0时，这个式子不成立。另外，由于n为奇数时，移动步数比偶数时少，因此我们得到tT(n)=O(n2)我们也许要问是否存在一个接受这个例子中的语言，且具有小得多的时间复杂性函数的图林机。答案是“是”和“否”。看起来好像图林机识别这个语言的字符串的移动步数应该是字符串长度的某个比例。图14.1所示的图林机的时间复杂性为平方的原因是磁带头反复来回移动，为了完成这个检验，看起来是必要的。存在直观的方法，在不修改整个方法的条件下，尽量减少来回移动的步数。比如，在第一阶段，我们可以一次性地将最左端的两个字母改写成大写符号，然后将最右端的两个符号改写成大写符号，如此进行下去。相似地，在最后匹配阶段，我们可以让图林机一次记住前半部分的两个符号，然后磁带头移动到后半部分作比较。两者合起来，这样的改进在稍微增加状态的条件下几乎减少了一半前后的移动。当然，如果能够从一次处理1个到1次处理2个，那么似乎1次处理4个更好，更进一步地，如果图林机能够记住整个前半部分的字符，我们可以避免所有无关移动。当然，没有办法做到这一点，因为状态数是有限的。我们只能做的是在某个很大的常数因子下减少运行时间，尽管我们可以让这个常数因子尽量大一些。任何一个需要扫描整个输入字符串的图林机，它的移动步数至少为n。对于这种语言，任何一个采用类似图14-1方法的图林机可能至少需要两倍或更多的移动。我们暂时的结论是我们也许只能将时间复杂性缩小到某个常数倍。这个结论被证明是正确的。而且，这个例子不存在特殊情况。通过增加状态数量或磁带符号（或两者都增加），对于任何一个图林机，我们都可以得到一个线性加快的图林机。对于空间复杂性，存在同样的结论。我们可以推断图林机处理某个特定字符串时需要的移动步数和占用的磁带格子的数量不是很有意义的指标，更有意义的指标是函数的增加率。常数倍降低时间复杂性后，结果仍然是平方级的增长率，并且能够证明任何一个单个磁带的图林机接受这个语言的时间复杂性都是平方级或更高。另一个降低时间复杂性的方法是增加磁带的数量，在上面例子中，两个磁带的图林机能够避免导致运行时间为平方级的来回移动，从而使得运行时间是线性关系。在更一般的例子中，不能总是期望增加磁带来得到线性的处理时间，参见练习14.14，增加磁带只可能将运行时间降低到它原来的平方根的程度。正如例子14.2揭示的，如果我们能够描述一个接受给定语言的图林机，那么时间复杂性的增长率在一定程度上说明了这个图林机所体现的算法的效率。如果我们有两个识别同样语言的图林机（并且这两个图林机具有相同的磁带数），那么我们认为时间复杂性的增长率更小的图林机更优（至少当输入字符串足够长时）。现在我们能够将上面的结论用于比较两个语言的复杂性或困难性。如果识别语言L1的k带图林机的时间复杂性是f1，识别语言L2的k带图林机的时间复杂性是f2，f2快于f1，那么认为L2比L1更复杂，或更难于识别是合理的。你也许期望非确定型图林机的时间和空间复杂性称为一个有用的概念。毕竟，一个NTM可以通过猜测处理字符串，从而达到快捷的方法。而且许多可解的、有趣的判定问题的解决方案用非确定型图林机来描述更清楚。我们将发现增加这个成分，对于根据复杂性对语言和判定问题的分类是有帮助的。定义14.3（非确定型图林机的时间和空间的复杂性）令T是一个非确定型图林机，它接受的语言是L*。对于输入字符串x，我们定义计算时间tx如下。首先，如果T在x上可能出现无限循环（注意只要存在这个可能，哪怕还存在停机），那么tx没有定义；否则如果xL，则tx是T在x上导致停机的最少移动步数，如果xL，那么tx是T在x上导致崩溃的最少移动步数。T的非确定型时间复杂性函数tT定义如下，tT(n)是所有长度为n的字符串x的最大的tx。因此，如果没有一个长度为n的字符串可能（再次注意，只有有一种可能）导致T无限循环，那么tT(n)是有定义的。换句话说，只要有一个一个长度为n的字符串可能（再次注意，只有有一种可能）导致T无限循环，那么tT(n)就是无定义的。类似地，如果T在x上存在无限循环，那么sx无定义；否则，如果xL，sx表示接受x的多个可能路径中，使用最少的磁带格子数量，如果xL，那么sx表示导致崩溃的使用最少的磁带格子数量。在确定型情况下，对于多带图林机，“磁带格子数量”含义是所有磁带上其中最多的一个磁带占用数量。T的非确定型空间复杂性sT定义如下，如果T在某个长度为n的字符串上可能有无限循环，则sT(n)无定义；否则sT(n)表示所有长度为n的字符串x中，最大的sx。这个定义没有第一次出现时那样难以理解。幸运的是，我们通常不需要关心tT和sT在某个点上无定义的情况。通常对于我们感兴趣的语言（或尽量要解决的判定问题），对应的图林机不会出现无限循环的情况。特别地，我们通常考虑满足tT=2, $wa,b*, |w|=1, x=wk分析：一个直观的识别这个语言的确定性方法是确定输入字符串x是否是wk的形式，且|w|=1，然后检查|w|=2的情况，.，直到|w|=|x|/2。图14.2的图林机是非确定型。描述这个图林机时，我们先忽略第一个成分Place($)，集中考虑其他部分，它们也是从磁带头放在0号格子开始。图林机移过输入字符串，在磁带上生成任意的字符串w，复制一份w，然后复制任意多次w，删除所有分开各个拷贝的空格，然后将生成的字符串与初始输入字符串比较。这里的非确定性体现在两个方面：1）生成字符串w；2）w复制的次数。如果输入字符串x是wk的形式，显然存在一个情况使得T停机，否则所有的比较最后导致崩溃。Place($)的目的是防止可能出现的无限循环，它可能出现在两个地方：w的生成和w的复制。Place($)在3n+2号格子放置一个特殊的符号，其中n是输入字符串的长度，由于图林机没有对于符号$的动作，因此如果磁带头移动到$右边的格子上，图林机崩溃。选择3n+2是针对一种极端的情况，|w|=1，且w被复制了n次，因此所有拷贝长度加上分隔它们的空格，共需要2n个磁带格子。如果我们坚持得到精确的答案，计算这个图林机的非确定型时间复杂性是比较复杂的。但是如果我们满足大O这种程度的答案，不是很复杂。如果生成的字符串w长度为m，共复制了k份，那么为了使得长度为n的输入字符串被接受，那么km=n。根据这一点，我们论述如下。移过输入字符串x并生成w，需要的时间大约是n+m的一定比例。复制每份w的时间是m2的比例，总共需要k-1次，因此时间大约是km2=mn。第一次删除空格需要时间m，第二次是2m，.,最后一次需要(k-1)m。因此删除空格的总时间是k2m=kn。最后，设生成（和复制）的字符串与输入字符串长度相同，都是n，比较它们需要的时间是n2的比例。因此整个过程的时间复杂性是O(n2)。上面NTM的空间复杂性很容易计算。用到的最右的磁带格子是w的最右一个拷贝的右端，这里，我们只考虑输入字符串被接受的情况，因此包括输入字符串占用的空间，总共用到的格子数是n+2+k(m+1)=2n+k+2，正如前面，k是w复制的份数。因为kn，因此图林机的空间复杂性是输入字符串长度的线性函数。例子14.3以一个简单的方法展示了我们后面将常常看到的问题。为了判定x是否属于某个语言，我们必须回答这样的问题：是否存在一个字符串w和整数k，使得x=wk？明显的确定型算法检查每个可能的w和k，来回到这个问题。而非确定型图林机能够通过猜测的方法避免算法的“每个可能选择”这样的性质，然后以确定的方式执行它猜测的选择。许多有趣的判定问题具有同样的通用形式：是否存在某个数值（或路径等）的选择，它能够成立？常常这样的问题预示了一个明显的非确定型方法：根据猜测选择值，然后测试它们观察它们是否成立。在许多类似上面例子的情况，如果T是一个回答这个问题的NTM，那么T的时间复杂性相当于检查这个可能答案的时间。这里存在一个假设，猜测选择哪个值去测试，所需的时间很有限。14.3 复杂性类现在，我们已经针对特定图林机定义了时间和空间的复杂性，我们能够开始讨论特定的计算问题的内在复杂性。正如第12章，我们对判定问题感兴趣。那些问题的每个实例可以编码成一个字符串，因此我们可以考虑肯定实例的编码组成的语言，并且我们可以通过考虑解决这个问题的任何图林机的复杂性来描述问题本身的复杂性。定义14.4中的复杂类是语言的类。在第12章，我们只考虑问题是否可解，没有考虑问题和它对应的语言之间的区别。任何一种编码方式都是可行的，只要它能够解码得到所表示的实例。现在，我们关心为了解决一个问题，需要多少时间和空间，因此我们应该更小心地对待所使用的编码方法。我们不希望由于编码和解码的难度极大地增加我们解决整个问题的难度。尽可能地，我们应该让选用的编码方法在这个意义上是合理的。定义14.4（基本复杂性类）对于函数f: NN，我们定义下面的复杂性类。1. Time(f)是一组语言的集合，其中每个语言都存在一个识别它的图林机T，且tT=f。2. Space(f)是一组语言的集合，其中每个语言都存在一个识别它的图林机T，且sT=f。3. NTime(f)是一组语言的集合，其中每个语言都存在一个识别它的非确定型图林机T，且非确定型时间复杂性函数tT=f。4. NSpace(f)是一组语言的集合，其中每个语言都存在一个识别它的非确定型图林机T，且非确定型空间复杂性函数sT=f。在上面4个定义中，都允许使用多带图林机。此处，我们引入了以后会用到的一些约定。一个图林机在扫描完输入字符串之前就停机或崩溃是完全可能的，因此它的时间复杂性可能小于n。但是更常见的情况是图林机扫描完整个输入字符串。在任何情况下，根据规则，识别语言的图林机需要擦掉磁带上的全部符号，只在1号格子留下答案0或1。因此对于一个长度为n的输入字符串，图林机至少需要2n+2步移动。我们用上面的Time(f)的表示Time(g)，其中g=max(f(n),2n+2)。为了保持移植性，其他三个符号也采用了类似的方便表示（对于空间复杂性情况，更常见的方法是考虑一个稍许不同的图林机模型，它具有一个只读的输入字符串磁带和一个或多个工作磁带，它的“空间”含义是占用的工作磁带的格子的数目，那么Space(f)中的函数f可能满足f(n)1，使得除了有限个整数外，都有f(n)Cn，则f是一个计步函数当且仅当计算f的时间在O(f)内（或者，存在计算f的图林机T，和一个常量K，使得对于每个n，T计算f(n)的步数不超过Kf(n)步）。我们省略这个证明。根据引理14.1，容易发现大多数熟悉的函数实际上是计步函数（参见练习14.17和14.18)。定义完了基本的复杂类，我们应该提醒大家存在“无限复杂”的语言，即存在不属于任何Time(f)和Space(f)（任给函数f）的语言，因为它们不能被任何图林机识别。但是，可解问题仍然可能是任意复杂的。定理14.3揭示时间复杂类的性质，它的证明使用了对角线参数法。定理14.3 令f: NN是任意的计步函数，那么对于某个常数C，Time(f)是Time(Cn2f2)的真子集。证明：我们只需要构造一个语言L，它属于Time(Cn2f2)，但不属于Time(f)。我们从9.7节的编码函数e开始，可以对它做一点直观的修改，使得它能够象对普通图林机那样，对多带图林机编码。令L=w0,1* | w=e(T), T是某个图林机（可能是多带），且T在输入w时，在f(|w|)步内崩溃如果L被某个图林机T1识别，且满足tT1=n，NSpace(f(n)Space(f2(n)。证明思路：我们需要确定地模拟一个f(n)空间的NTM。简单的方法是一个一个地试遍NTM的所有计算分支。这种模拟要求记录当前正在尝试的是哪一个分支，以便能够过渡到下一个分支。但是消耗f(n)空间的一个分支可能运行2O(f(n)步，每一步都可能是非确定的选择。顺序考察每一个分支要求记录某个具体分支上所做的所有选择，以便能找到下一个分支。所以改方法可能用掉2O(f(n)空间，超过了我们的目标O(f2(n)空间。改用另一种方法，考虑下面更一般的问题。给定NTM的两个格局c1,c2，以及一个数t，要求判定该NTM能否在t步内从c1转移到c2。称此问题为可产生性问题。如果让c1是初始格局，c2是接受格局，t是非确定型图林机所使用的最大步数，那么通过求解可产生性问题，就能判定机器是否接受输入。给出一个确定的递归算法来求解可产生性问题。它的运算过程是：寻找一个中间格局cm，递归检查c1能够在t/2步内到达cm，以及cm能否在t/2步内到达c2。重用两次递归检查的空间就可以显著地节省空间开销。该算法需要空间来存储递归栈。递归的每一层需要O(f(n)空间来存储一个格局。递归的深度是logt，这里t是非确定型图林机在所有分支上可能消耗的最大时间。有t=2O(f(n)，所以logt=O(f(n)。因此确定的模拟过程需要O(f2(n)的空间。证明：设N是在空间f(n)内判定语言A的NTM。构造一个判定A的确定型图林机M。M利用过程CANYIELD，改过程检查N的一个格局是否能在指定步数内产生另一个格局，它求解在证明思路中描述的可产生性问题。设w是输入N的字符串，对于N在w上的格局c1,c2以及整数t，如果从格局c1出发，N有一系列非确定的选择能使它在t步内进入格局c2，则CANYIELD输出1否则0。现在定义M来如下模拟N。首先修改N，使得当接受时，它把带子清空，把读写头移到最左边的格子，从而进入caccept格局。令cstart是N在w上的初始格局。选一个常数d，使得N在f(n)空间上的格局数不超过2df(n)，其中n是w的长度。2df(n)是N在w上的所有分支的运行时间的上界。M=“对输入w：1）输出CANYIELD(cstart,caccept,2df(n)的结果。”算法CANYIELD显然求解了可产生性问题，因此M正确地模拟了N。需要分析M，证明它在O(f2(n)空间内运行。每次CANYIELD递归地调用自己时，它都把c1,c2,t的值存储在栈中，以便这些值在从递归调用返回时能够得以恢复。因此递归的每一层需要补充O(f(n)空间，此外递归的每一层把t的值减小一半，开始时t等于2df(n)，所以递归的深度是O(log2df(n)=O(f(n)。因此全部空间消耗是O(f2(n)，正如所断言。在这个论证过程中，有一个技术难点，原因是算法M在调用CANYIELD时需要知道f(n)的值。为了克服这个困难，可以修改M，使它尝试每一个f(n)=1,2,3,.。对于每个f(n)=i，修改后的算法利用CANYIELD来确定接受格局是否可达，并且通过检查N能够从初始格局出发到达某个长度为i的格局，来确定N是否至少需要空间大小i。如果接受格局可达，M接受；如果没有长为i的格局可达，M拒绝；否则M继续尝试f(n)=i+1（也可以用另一种方法来克服这种困难，即假定M能在空间O(f(n)内计算出f(n)，但是那样就需要把这个假定加入到定理的陈述中。）-END-14 测度和复杂性分类14.1 函数的增长率计算复杂性问题研究一个计算模型在解决一个问题中需要的资源的数量，资源一般包括时间和空间两类。一般地，一个问题计算中需要的资源与其输入参数有很大关系，而我们的标准应该独立于参数，只关注问题本身，能够衡量在整个（或绝大部分）输入参数域的资源消耗，因此一个好的标准是资源消耗在整个参数域的增长率。定义14.1 f, g都是从自然数集N到N的部分函数，则：1）如果存在常数C和n0，对于每个f和g都定义的n=n0，都有f(n)=n0，都有f(n)=Cg(n)，则称f(n)=o(g(n)，或f=o(g)；（读作小Oh）3）如果f=O(g)且g=O(f)，则f=Q(g)。（读作大theta）1）和2）都表示g最终会比f大，区别是2）表示g增长比f快得多，f/g将趋于0，当n足够大时，f与g相比可以忽略不计；1）表示f/g趋向小于一个常数；3）则表示f/g的趋向既有上界，又有下界，可以认为它们增长率相同。更准确的写法是，O(g)表示一个集合，fO(g)，记为f=O(g)是为了方便，此处“=”表示关系，而不是相等或程序设计语言中的赋值。下列显然成立：如果f=o(g)，则f=O(g)；如果f=O(g)且fo(g)，则f=Q(g)；如果f=o(g)，则gO(f)。定理14.1 关系R1定义为，f R1 g当且仅当f=O(g)，fg，满足反身性和传递性；关系R2定义为，f R2 g当且仅当f=o(g)，f=0，a_k0有意义。指数函数形如：q(n)=a-n对本书内容而言，a1有意义。定理14.2 p是多项式函数，q是指数函数，则：p(n)=Q(n-k)p=o(q)证明：1）lim(p(n)/n-k)=a_k，a_k是常数2）证明lim(n-k/a-n)=0。14.2 Turing机的时间和空间复杂性定义14.2（Turing机的时间和空间复杂性）T是一个TM，T的时间复杂性是一个定义在自然数上的函数t_T，t_T(n)表示长度为n的输入字符串引发的最大移动步数。如果存在一个字符串x，|x|=n，T在判定中进入无限循环，则t_T(n)为无穷大，或称无定义。类似定义T的空间复杂性函数s_T，s_T(n)表示长度为n的输入字符串引发的最大磁带使用空间（格数）（如果是多带TM，则取单个磁带的最大空间，不是所有磁带空间的总和），如果T在判定中进入无限循环，且使用了无限多的磁带空间，则称s_T(n)为无穷大，或无定义。如果语言L1能够被一个k-带TM识别，时间复杂性是f1，如果任何一个识别语言L2的k-带TM的时间复杂性函数都比f1增长快，则称L2比L1复杂，或L2比L1更难识别。定义14.3（非确定型Turing机的时间和空间复杂性）T是一个NTM，先定义t_x，对于输入字符串x，如果可能引起T无限循环，则t_x无穷大，或无定义；如果xL(T)，则t_x是T到达停机状态的最少移动步骤；如果xL，t_x是T到达崩溃状态的最少移动步骤。再定义非确定型时间复杂性函数t_T，t_T(n)是所有长度为n的字符串产生的最大t_x，因此如果存在一个长度为n的字符串导致T无限循环，则t_T(n)无定