皇帝新脑-第22章
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 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）。如果需要的话，哈密顿线路可由这些边缘的子集给出，它用具有比前述的更多个零的二进位序列来描写。检查过程是可以比开始找这些哈密顿线路更迅速地完成的事。人们所要做的一切，是检查提出的线路的确是一线路，也就是边缘须属于原先的图，而图中的每一顶点刚好只被用过两次，在两个边缘的一个顶点各一次。这一检验过程是某种可以在多项式时间内完成的事。
事实上，这个问题不仅是NP的，而且被认为是NP完备的。这表明其他任何NP问题都可在多项式时间内转变成它。这样，如果某个足够聪明的人能在多项式时间内找到解决哈密顿线路的算法，也就是能显示哈密顿线路问题实际上是在P中！则其推论是任何 NP问题都在P中！这样的事情会具有重大的含义。一般地讲，对于合情理大的nP中的问题被认为可以用一台快速的现代电脑“处理”的（也就是“在一可接受的”时间长度里是可解的）。 而在NP中又不在P中的问题， 对于合情理大的n被认为是 “不可处理的”（也就是虽然在原则上可解，“在实际上是不可解的”），而不管我们将面临着何种可以预见的种类的电脑速度的增加。（对于大的n的不在P中的NP问题，需要的时间会急速地变得比宇宙的年龄还要长，这对于实际的问题没有什么用处！）任何在多项式时间内解决哈密顿线路问题的聪明算法都能转换成在多项式时间内解决任何其他NP问题的算法！
另一个NP完备的15问题是“旅行推销员的问题”。这个问题和哈密顿线路问题很相像，除了在不同的边缘附上数字，人们寻求数（推销员走的“距离”）的和为极小的哈密顿线路。旅行推销员问题的多项式时间解会又一次导致所有其他NP问题的多项式时间解。 （如果真的找到这样的一个解，将会变成头条新闻！尤其是好几年来提出了密码系统，该问题有赖于大整数的因子化问题，这是另一种NP问题。如果可在多项式时间内解决这一问题，那么这样的码就可能被强大的现代电脑所破。但是如果不能，这码就是安全的。参见伽特纳1989。）专家们普遍相信，不管用任何类图灵机的仪器，实际上都不可能在多项式时间内解决一个NP完备的问题。所以结论是，P和NP不是同样的这个信念很可能是正确的，虽然还没有一个人能证明之。这仍然是复杂性理论最重要的未解决问题。物理事物中的复杂性和可计算性复杂性理论对于本书的讨论是重要的，因为它引起了另外的问题，和事物是否可计算的问题有一点区别；也就是说，被认为是算法的事物实际上是否以一种有用的方式为算法的。在后面的章节中，我关于复杂性理论将讲得比可计算性更少。因为我倾向于认为（虽然毫无疑问地是在相当不足够的基础上）复杂性理论的问题和可计算性本身的问题不一样，在和精神现象相关联上不占有中心的地位。而且，我感到算法的可行性问题的现状才刚刚被复杂性理论所触及。
然而，关于复杂性作用的问题，我也很可能是错的。正如我将在后面（第九章464页）评论的那样，实在物理对象的复杂性理论也许和我们刚刚讨论的有显著的不同。为了使这种差异变得更明了，那就必须使用量子力学，这个原子、分子以及许多其他在大得多的尺度下重要现象行为的神秘而强有力的精确理论。 在第六章我们将遇到这一理论。 按照最近大卫？德义奇（1985）提出的一系列思想，在原则上可能建造“量子电脑”，存在不属于P的然而由这种装置可在多项式时间内解的问题的（类）。直到现在一点也不清楚，一个实际的物理仪器如何建造成行为可靠的量子电脑，而且迄今所考虑的问题的类肯定是很人为的――但是，我们似乎已经知道了用量子物理仪器改善图灵机的理论可能性。
我在这里讨论时把它当作一台“物理仪器”的人类的头脑，尽管是设计得非常微妙精巧的，而且是非常复杂，它本身会从量子理论的魔术中得到好处吗？我们是否理解量子效应可以用于解决问题或作判断的方式呢？
为了利用这种潜在的好处，我们也许必须“超越”现存的量子理论，这是可以理喻的吗？实际物理仪器真的很可能改善图灵机的复杂性理论吗？实际物理仪器的可计算性理论又是如何呢？
为了研究这类问题，我们必须离开纯粹数学的领域，并在下面的章节中探求物理世界在实际上是如何行为的！注 释1．在考虑其成员又为集合的集�
