表出是无关紧要的，我们的边缘是否互相穿越还是处于三维空间中都是无所谓的。）哈密顿线路简单地就是一个只包括图的边缘的闭合圈，其中每一顶点只刚好通过一次。图 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．在考虑其成员又为集合的集合时，我们必须小心地区别那个集的成员以及那个集的成员的成员。例如，假定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，这一步骤的数目可用一些技巧减少到nlogloglogn――这当然还在P中。参见克奴斯（1981）有关的更多资料。14．更正确地讲，只对是/非类型问题（例如，给定a，b和c，a×b=c为真的吗？）P、NP和NP完备的族（参见165页）才被定义，但在正文中的描述对我们的目的已经足够。
15．严格地讲，我们需要是/非的模式，诸如：推销员是否有一条距离小于若干的路径呢？（见上面的注释14）。
第五章经典世界物理理论的状况
为了了解意识如何是自然的一部分，我们对自然的运行要知道哪些呢？制约身体和头脑组成基元的定律与此关系重大吗？如果真的像许多人工智能的拥护者所竭力说服我们的那样，意识理解仅仅是由算法所规定的，那么这些定律实际上是什么样子的则是无关紧要的。任何能够实现算法的仪器都一样好。另一方面，也许我们的知觉比可怜的算法更富有内容。
也许构成我们的确切方式正和实际上制约构成我们物质的物理定律一样重要。我们也许需要理解构成物体物质以及规定所有物体行为的根本性质。物理学尚未做到这一步。许许多多的秘密还有待揭示和探索。然而，大多数物理学家和生理学家却断言，我们已经拥有足够的关于通常尺度的、诸如人脑物体运作的物理定律的知识。作为一个物理系统，大脑毫无�