按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
婴儿”心脏线形状，后者出现在图3。2的左边的地方――也就是图3。1的主要区域――在图4。13中标作C3的区域。这些（一起或分开的）区域由于上述公式的存在又组成了递归可列集。
尽管我已经做过假设，即孟德勒伯洛特集可能是非递归的，我们运用某些定义完好的以及不过于复杂的算法，可以清理出该集合的最大面积。这个步骤似乎应该继续下去。集合中所有最明显的、肯定占满了它面积的绝大部分（如果不是所有的话）的区域，可以被算法地处理。如果正如我所设想的那样，这集合全体不是递归的，则我们的算法不能达到的区域必须是非常精巧的，并且很难找到。而且，当我们已经定位了这样的一个区域，看看有无机会改善我们的算法，使那些特殊的区域也能达到。然而 （如果我关于非递归性的假设是正确的），还会有其他这类区域躲藏在微妙的、复杂的、模糊的深处，甚至于用我们改善了的算法都达不到。我们再次可能利用直觉、天才和勤奋的巨大努力，将这样的一个区域定位，但是还会有其他的会逃脱掉，等等。我想这就像用数学方式处理困难的问题，且假定为非递归性的。人们在某些特别的领域遇到的最普遍问题可由简单的算法步骤――甚至是已经知道了几世纪的步骤来解决。但是其中仍有漏网之鱼，要掌握它们就需要更复杂的步骤。漏网之鱼当然特别刺激数学家们，并促使他们去发展更为有力的方法。这些必须是基于对涉及的数学性质的越来越深刻的洞察之上。在我们对物理世界的理解中也许存在某些这种东西。在上面考虑的词语及镶嵌问题中，人们可以对这一类事稍有了解（虽然在这些领域中数学工具还未发展得非常远）。我们在一个非常特殊的情形下能用非常简单的论证去显示，某一词不能用允许的规则从另一词得到。不难想象，更复杂得多的推理可在处理更古怪的情形时起作用。很可能这些新的推理可发展成算法步骤。我们知道，不存在一个可以足够应付词语问题的所有情况的步骤，但是逃脱的例子需要非常仔细和精巧地去构造。的确，只要我们肯定知道躲开我们算法的例子，只要我们知道如何构造这些例子，则我们可以改善我们的算法以包括这种情形。只有不“相等”的配对词会逃脱，故一旦我们知道它们逃脱，我们就知道它们不“相等”，这一事实可添加到我们算法上去。我们改善了的洞察就导致一个改善了的算法！复杂性理论我在前面以及上一章关于算法的性质、存在和局限的论证是处于非常“原则的”水平上。我根本就没有讨论到出现的算法是否在任何方面像是可行的。即使对于算法存在并且该算法如何构造都很清楚的问题，也还需要许多才干和勤勉，才能将此算法发展成有用的东西。有时小小的洞察和才干就能可观地降低算法的复杂性，以及有时极大地加快其速度。这些问题经常是非常细节和技术性的。近年人们在构造、理解和改善算法方面，在不同的情况下做了大量的工作。这是一个快速扩大和发展的研究领域。我不想对这些问题进行细致的讨论。然而，有关算法的速度可被增加的某一绝对的极限有各种普遍知道或猜测的东西。人们发现，甚至在具有算法性质的数学问题中，也存在种种内在地比其他问题更难于算法地解决的问题。困难的问题只能用非常慢的算法（或许，需要非同寻常地大量的存储空间等）来解。有关这类问题的理论称为复杂性理论。
复杂性理论并不这么关心算法地解决单独问题的困难，而是关心无限个问题的族，找到解决一个单独族的所有问题的一般算法。族中的不同问题会有不同的“尺度”。问题的尺度是由某一自然数n来测量。（关于这一个数n实际上如何表征问题的尺度，我一会儿还要再说。）算法对于每类中的每一特别问题所需的时间长度――或更正确地说，基本步骤的数目――是依赖于n的某一自然数N。稍微精确一点讲，我们讲在所有具有某一特别尺度n的问题中算法采用的最大的步骤数目为N。现在，当n变得越来越大，N也似乎变得越来越大。事实上，N似乎增加得比n快速得多。例如，N可以近似地和n2，n3或许2n成比例（对于大的n，它比n，n2，n3，n4以及n5中的每一个都大多了，甚至比带有任何固定指数r的nr都大），或者譬如讲N甚至近似地和22n（这又更大得多）成比例。
当然，这些“步骤”的数目可依赖于实现该算法的电脑的类型。如果电脑为第二章描述的图灵机，那儿只有一盘磁带――这是相当低效率的――那数目N就会比允许两盘或三盘磁带的增加得更快速（也就是说机器会运行得更慢）。为了避免这类不定性，按照N作为n的函数增加的可能方式进行了宽广的分类，使得不管使用何种类型的图灵机，N的增加率的度量总是归到同一分类中去。一种称为P（说明“多项式时间”的分类包括了所有最多为n，n2，n3，n4，n5，…中的一个的固定倍数①的速率。也就是说，对P分类中的任何问题（这里我的“问题”的真正含义是具有解决它们的一个一般算法的一族问题），我们有N≤K×nr，① 这是在39页提到的希尔伯特第十问题的负面答案。（例如，参见德弗林1988。）这里变量的个数是不受限制的。然而人们知道，为了使这种非算法性质成立，实际上需要变量的个数不超过九就可以。这儿K和r为常数（与n无关）。这表明N不比n的某一固定方次的某一倍数更大。
两个数相乘肯定是属于P问题的简单类型。为了解释这一点，我必须首先描述数目n如何表征一对特殊乘数的尺度。我们可以想象每一个数都以二进位写出，而每一个数的二进位位数简单地为n/2，总共给出了n二进位数――也就是总共n比特。（如果一个数比另一个短，可以简单地从短的开始连续地在前头加上零使之和长的具有一样的长度。）例如，如果n=14，我们可以考虑1011010×0011011（就是1011010×11011，但是在短的数上添了一些零）。最直接进行乘法的方式是只要写出：
记住，在二进位系统中，0×0=0， 0×1=0，1×0=0， 1×1=1，0＋0=0， 0＋1=1，1＋0=1，1＋1=10。单独二进位乘法的次数为（n/2）×（n/2）=n2/4，并且可具有（n2/4…（n/2）次的单独的二进位加法（包括移位）。这样，总共有（n2/2）…（n/2）次的单独算术运算――我们必须包括一些涉及到移位的额外的逻辑步骤。总的步骤数为N=n2/2（忽略低阶项），这肯定是多项式的13。
一般来说，对于一族问题，我们取这问题的“尺度”的测度n为需要指明该特别尺度的问题的自由数据所需要的二进位位数（或比特）的总数。这意味着，对于给定的n，在给定的尺度下问题会有多到2n种不同的情形 （因为每一位可有两种可能性中的任一个， 0或1，而总共有n位数），而这些都必须由算法在不多于N步骤下被一致地处理好。
存在许多不属于P问题（的族）的例子。例如，为了进行从自然数r计算 的运算，甚至只要写出这一答案就大约需要 步骤，且不说进 2 ＇ 2 2 nr行计算了。 为在 的二进位表示中的位数。计算 的运算，只要写下就 n r 222r需要 步骤等等！这些比多项式大多了，所以肯定不在 中！ 2 P 2r在多项式时间内可以写下答案并甚至能检查正确与否的问题更为有趣。由此性质表征的（可算法地解出的）问题（的族）是一个重要的范畴。它们被称为NP问题（的族）。更精确地讲，如果在NP中的问题的族的个别问题有一解，那么该算法将给出这个解，并且它必须能在多项式时间内检验所设想的解确实是一个解。在问题没有解的情形下，算法会告诉我们这个，人们不必在多项式或别的时间内去检验的确没有解14。NP问题既在数学本身，也在实在世界的许多范围内出现。我只给出一个简单的数学例子：在一个图中寻找所谓的“哈密顿线路”的问题（一个极简单思想的吓唬人的名字）。用“图”来表示点或“顶点”的有限集合，一定数目的点对由称为图的“边缘”的线连接起来。（我们在这儿并不对几何或“距离”性质感兴趣，只对由哪一顶点连接到哪一顶点感兴趣。这样，所有顶点是否在一个平面上表出是无关紧要的，我们的边缘是否互相穿越还是处于三维空间中都是无所谓的。）哈密顿线路简单地就是一个只包括图的边缘的闭合圈，其中每一顶点只刚好通过一次。图 4。14中画出了一个在上面标出哈密顿线路的图。哈密顿线路问题是去决定，对于任何给定的图是否存在哈密顿线路，只要存在就把它明了地画出来。
图4。14带有（用稍粗一些的黑线）标出的哈密顿线路的一个图。还只存在另一条哈密顿线路，读者也许介意把它找出来。可以按二进位用不同方式来表述一个图。用何种方法关系不大。一个步骤是给顶点编上号1，2，3，4，5，…，然后以某种适当的固定顺序列出成对的顶点来：
（1，2），（1，3），（2，3），（1，4），（2，4），（3，4），（1，5），（2，5），（3，5），（4，5），（1，6），…然后我们做一个准确的0和1的搭配的表，当一对顶点对应于图的一个边缘时写上1，否则写0。这样二进位序列10010110110…
表明顶点1接到顶点2、顶点4以及顶点5，…顶点3接到顶点4和顶点5，…，顶点4接到顶点5，…等等（见图4。14）。如果需要的话，哈密顿线路可由这些边缘的子集给出，它用具有比前述的更多个零的二进位序列来描写。检查过程是可以比开始找这些哈密顿线路更迅速地完成的事。人们所要做的一切，是检查提出的线路的确是一线路，也就是边缘须属于原先的图，而图中的每一顶点刚好只被用过两次，在两个边缘的一个顶