按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
出的线路的确是一线路，也就是边缘须属于原先的图，而图中的每一顶点刚好只被用过两次，在两个边缘的一个顶点各一次。这一检验过程是某种可以在多项式时间内完成的事。
事实上，这个问题不仅是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．在考虑其成员又为集合的集合时，我们必须小心地区别那个集的成员以及那个集的成员的成员。例如，假定S是另一确定的集T的非空子集的集合，而T的元素是一个苹果和一个桔子。T就有“二性”而非“三性”的性质；但是S实际上有“三性”的性质；S的三个成员是：一个只包括一个苹果的集合，一个只包括一个桔子的集合以及包括一个苹果和一个桔子的集合――总共有三个集，这就是S的三个元素。类似地，其成员只有空集的集合具有“一性”而非“零性”――它有一个成员，也就是空集！空集本身当然只有零个成员。
2．事实上，哥德尔定理的推理可以用这种方式来表达，使之不依赖于诸如Pk（k）的命题“真理”的完全外在的概念。然而，它仍然依赖于某些符号的实在“意义”的解释：尤其是，“～ ”的真正 是“不存 意义在（自然数）……使得……”。
3．在下面用小写字母代表自然数，而用大写字母代表自然数的有限集合。令m…→〔n，k，r〕表示陈述“如果x=｛0，1…，m｝，它的k个元素的每一子集都被放到r个盒子里，则存在X的一个“大”的至少包含n个元素的子集Y， 使得所有Y的k元素子集都被放到同一盒里去。” 这儿 “大”的意思是Y中的元素数目比作为Y中的元素的最小的自然数还大。考虑如下命题： “对于任何选取的k，r和n，存在一个m0，使得所有大于m0的m，陈述m…→〔n，k，r〕总成立。”J？巴黎斯和L？哈林顿（1977）指出这一命题等效于算术的标准的（皮阿诺）公理的哥德尔型命题。这一道命题是不能从那些公理证明得到的，但是关于那些公理作了某些“显然正确”的断言正也就是，在这种情形下，从公理推断出来的命题本身是真的）。4．其题目为《基于序数的逻辑系统》，而且有些记者将会熟悉我用在下角标示代表康托序数的记号。使用我在上面所描述的步骤得到的逻辑系统的等级由可计算的序数来表征。
存在一些相当自然的和容易陈述的数学定理，如果人们试图用标准的算术的（皮阿诺）法则去证明，就需要使用在前面概述的“哥德尔化”步骤。这些定理的数学证明根本就不依赖于任何模糊或可疑的似乎处于正常数学论证的步骤以外那一类推理。参见斯莫林斯基（1983）。的最 “极端的” 的数学陈述 （虽然人们还经常考虑比这更极端得多的陈述）。
连续统假设，由于哥德尔本人和保罗J？柯亨确立了它实际上和集论的标准公理和步骤法则无关，而变得格外有趣。这样，对连续统假设的看法可用来区分形式主义者和柏拉图主义者。对于一个形式主义者而言，由于用标准的（策墨罗――弗兰克尔）形式系统既不能建立也不能否定连续统假设，所以是“非决定的”，把它叫做“真”的或“伪”的都“没有意义”。
然而，对于一个好的柏拉图主义者，连续统假设或是真的或是伪的，但为了确立它就需要某种新的推理形式――实际上甚至超出了对策墨罗――弗兰克尔形式系统使用哥德尔型命题的手段。（柯亨（1966）本人提出一种使得连续统假设成为“显然错误”的反思原则！）6．参阅鲁克尔（1984）的生动而不太技术性的有关论述。
7．伯鲁尔本人似乎部分地因为对自己的一个拓朴学的 “伯鲁尔固定点定理”证明的“不可构造性”忧虑，而开始沿着这个思路思考的。该定理断言，如果你取一个圆盘――也就是一个圆和它的内部――并且以一种连续的方式运动到它原先定位的区域的内部，那么在圆盘上至少有一叫做固定点的点，它刚好在自己开始的那点结束。人们也许不知该点准确地在何处，或者也许那里有许多这类的点，这个定理只是断言某一这类的点的存在。作为数学的存在定理而言，这实际上是一个相当“构造性的”定理。依赖于所谓的“选择公理”或“卓恩引理”的存在定理具有不同程度的非构造性 （参阅柯亨1966，鲁克尔1984）。伯鲁尔情形的困难和下面相类似：如果f为一实变量的实数值的连续函数，该函数既取有负值又取有正值，找到f取零值的地方。其通常的步骤是涉及到重复地对分f改变符号的区划。但是去决定f的中间值为正、负或零，在伯鲁尔需要的意义上可以不是“构造性的”。8．我们列出集合｛v，w，x，…，z｝，这里按照某种字典方案，v代表函数f。我们在每一阶段（递归地）检验看是否有f（w，x，…，z）=0，并且只有如果是这样的话，才维持命题 ， ，… 〔 ， ，…， w x z f（w xz）=0〕。9．最近妮诺？伯龙（由于受这本书初版精装本中我的议论所刺激）告诉我，她已能断定孟德勒伯洛特集（的补集）在下面注释10的特殊意义下的确是非递归的，正如我在正文中所猜测的那样。
10．存在实变量的实函数的可计算性的一种新理论（和传统的自然数变量的自然数函数相反），由伯龙、苏伯和斯马勒（1989）提出。我最近才注意到该理论的细节。该理论还适用于复函数，它可能和正文中提出的问题有重要的关系。这一新工作的一些结果赋予孟德勒伯洛特集在适当意义下为非递归的猜测以强大的支持。
11．这一特殊问题可更正确地被称为“半群的词语问题”。还有其他形式的词语问题，其法则略为不同，我们在此不予关注。12．汉弗（1974）和迈尔斯（1974）还指出，存在一个单独的（一个巨大数目的花砖）集合，它只能以不可计算的方式来镶嵌平面。13．事实上对于大的n，这一步骤