按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
募螹的特征函数fM定义为fM（x）＝1，如果x是M的一个元素，否则fM（x）＝0。因此，子集M被定义为有效可决定的，如果其特征函数对于一个数无论是否属于M，都是有效可计算的（或递归的）。
集合M定义为有效（递归）可计数的，如果存在有效（递归）程序f可相继地产生出其元素（对于M中所有元素x1，x2，…，有形式f（1）＝x1，f（2）＝x2，……）。容易证明，所有递归（可决定的）集都是递归上可计数的（或递归的）。但是，存在着这样的集合，它是递归上可计数的，但却不是可决定的。这是第一条线索，它意味着，莱布尼茨的基于通用可决定程序信念的乐观纲领存在着局限性。
对于自然智能和人工智能，有效可计算性范式意味着精神是由程序控制机器表示的。神经结构涉及的是符号数据结构，而精神过程也就是操作算法。历史上，AI的核心是在1956年的达特茅斯会议期间建立起来的。参加会议的约翰·麦卡锡、阿兰·纽厄尔、赫伯特·西蒙以及来自其他不同学科领域的一流研究人员，形成了新的AI科学共同体。他们都受到图林的“机器能否思维？”问题的启发，这个问题是图林在著名的《计算机器和智能》（1950）一文中提出来的。
在莱布尼茨的通用数学的传统中，人们可能会相信，人的思维可以用某种通用演算来形式化。在其现代的翻版中，人们可能会假定，人的思维可以用某种强有力的形式编程语言来表示。无论如何，形式表达式都是符号序列，是可以用自然数进行编码的。于是，对于对象的断言就相应于关于数字的函数，结论就将从某种有效的计数程序中得出，如此等等。实际上，现代计算机的机器语言就是由数字序列构成的，对于机器的每一状态和程序进行了编码。因此，计算机的操作可以描述为有效的或递归的数字程序。
如果人的思维可以用递归函数来表示，那么按照丘奇公设，它就可用图林程序来表示，而图林程序可以用图林机计算。因此，人的思维也就可以用通用计算机来加以模拟，在此意义上，对于图林提出的问题也就必定要回答“是”。人的思维是可以编码、可用递归程序来表示的，这一前提当然是可疑的。甚至数学思维的过程也可以远比递归函数更为复杂。按照丘奇的公设，递归性或图林可计算性仅仅是可计算性的一种理论限度。
下面我们希望考虑在这种限度之下和之上的复杂性程度问题。在这种限度之下，有许多涉及到一定限度的实际问题，其限度涉及到如何增加算法的速度。特别是在数学问题中，有一些种类的问题，它们的算法求解本来要比解决其他一些问题困难得多。因此，图林机有不同程度的可计算性，计算机科学中的复杂性理论使之精确化。
问题（或相应的函数）的复杂性分类可以由复杂性程度来标志，这给出了函数的阶，函数描述了依赖于其输入长度的算法（或计算程序）的计算时间（或基本计算步骤的数目）。输入的长度可以用十进制的数目来度量。按照计算机的机器语言，可以方便地将十进制数字编码成仅仅用0和1的二进制码，并用二进制字符来定义其长度。例如，3的二进制码是11，其长度为2。函数f具有线性的计算时间，如果f的计算时间不大于c·n，其中n是输入长度，c是常数。
两个（二进制）数的加法显然只具有线性计算时间，例如，对于3＋7＝10中应的二进制计算
0 1 1
1 1 1
__________________
1 0 1 1
其中需要5个基本计算步骤把两个二进制数加和（包括运算）。我们提醒读者，加和二进制数字相加的基本步骤是0＋0＝0，0＋1＝1，1＋1＝10，以及运算。可以方便地假定，两个将要相加的数具有同等长度。否则，我们简单地把较短的数加上一系列的零，例如，111和011而不是和11。一般地，如果将要相加的特定的数对的长度为n，则一个数的长度为n/2，因此，我们需要不大于n/2＋n/2＝n个基本计算步骤，其中包括了运算。
函数f具有二次计算时间，如果对于所有的长度为n的输入和常数c，f的计算时间不大于c·n2。
一个简单的二次计算时间的例子是两（二）数相乘。例如，对于7·3二21，相应的二进制计算：
1 1 1·0 1 1
___________________
0 0 0
1 1 1
1 1 1
——————————
1 0 1 0 1
按照前面的约定，我们有n＝6。基本二进制乘法的步数是n／2·n／2＝n＇2＇／4。包括进运算，基本二进制相加的步数是n／2·n／2－n／2＝n2／4－n／2。总起来，我们得到n2／4＋n2／4－n／2＝n2／2－n／2，它小于n2/2。
函数f具有多项式计算时间，如果f的计算时间不大于c·nk，假定它是多项式P（n）的首项。函数f具有指数计算时间，如果f的计算时间不大于c·2P（n）。许多实际的和理论的问题都属于这种P复杂性，所有P类函数都是可以用确定论的图林机在多项式时间中加以计算。
数学史上有一些优美的图论问题可以说明复杂性理论的基本概念。1736年，著名的数学家利昂纳德·欧拉（1707－1783）解决了图论中的第一个问题。在东普鲁士的首都柯尼斯堡，所谓的老普里戈尔河和新普里戈尔河在普里戈尔河连接起来了。在18世纪，河上建造了7座桥，把南面s、北面n、东面e与小岛i联系起来（图5．3）。是否有这样一条路线，即每座桥只走一次而可以返回到最初的起点？
欧拉把问题归结为图论。区域n，s，i，e用图的顶点来代替了，在两个区域之间的桥用相应顶点之间的边来代替（图5．3b）。
在图论的语言中，欧拉的问题就成为，对于每一顶点，是否存在一条线路，它仅仅通过每一条边一次而最终返回到起点（“欧拉环”）。对于任意的图形，欧拉证明：欧拉环存在，当且仅当每一顶点都具有偶数条边（“欧拉条件”）。对于图5．3a，它并不满足这种条件，因此在这里欧拉问题不可能有解。一般地，存在用欧拉条件来检验任意的图的算法，如果它是欧拉环。算法的输入包括所有顶点1，…，n的集合V，所有边的集合E，它是所有顶点对的集合的子集。这种算法的计算时间线性地依赖于图的大小，它由定点数和边数之和来定义。
1859年，数学家威廉姆·哈密顿（1805－1865）引入了一个颇为类似的问题，但比欧拉的问题更复杂。哈密顿考虑的是任意的图，它仅仅意味着有限的顶点的集合，通过边联系起来的一定数目的顶点对。哈密顿问题是：是否有一个通过每一顶点（而不是欧拉问题中的通过每一边）的封闭环（“哈密顿环”）。图5。3c示意了有一个哈密顿环的图，其中按照数字顺序通过每一顶点。
不过，与欧拉问题的情形不同，我们并不知道这样的条件：它精确地表明一个图中是否包含哈密顿环。我们仅仅能够定义一种算法，来检验任意的图是否包含有哈密顿环。该算法检验所有的顶点的排列，以确定它们是否形成了一个哈密顿环。由于n个顶点有n！种不同的排列，该算法找到某个解的步骤不大于c·n！，其中c是常数。容易证明，n！阶相应于n＇n＇阶。结果是，对于哈密顿问题，一个算法需要指数的计算时间，而欧拉问题的算法求解需要的是线性计算时间。因此，哈密顿问题实际上是计算机无法解决的，甚至对于小的数目n也如此。
大的计算时间的主要原因在于，确定论的计算机只能一步步地对于其中巨大数量的一个个情形进行检验。更方便的是运用非确定论的计算机，它允许在有限的可能数目中随机地选择计算程序，而不是以系列的方式一步步地进行。让我们再一次考虑哈密顿问题。假定一个输人图具有n个顶点u1，…，un。一个非确定论的算法以非确定论的、随机的方式选择了一定的顶点顺序Vi1，…，Vin。然后，该算法进行检验：这种顺序是否形成了一个哈密顿环。问题也就是，对于所有的数字j（j＝1，…，n－1），相继的顶点Vij和Vij＋1以及起初的开始顶点Vin和Vi1是否是由边联系起来的。这种非确定论算法的计算时间线性地依赖于图的大小。
一般地说，NP意味着这样类型的函数的复杂性，它们用非确定论图林机进�