算时间线性地依赖于图的大小。
一般地说，NP意味着这样类型的函数的复杂性，它们用非确定论图林机进行计算时需要多项式时间。哈密顿问题是一个NP问题的例子。另一个NP问题是“旅行推销员问题”，除了种种边都有一定的数目规定以外，它与哈密顿问题非常相似。人们要解决的是：对于这一问题的哈密顿环，找出其数字的和的极小值，或更直觉地说，找出其旅行的距离的极小值。
所有的P问题由定义，都是NP问题。但是，复杂性理论的关键性问题在于是否有P＝NP，或换言之，由非确定论计算机以多项式时间解决的问题，是否也可以由确定论计算机以多项式时间来加以解决。
哈密顿问题和旅行推销员问题，是所谓的NP完全问题的例子。这意味着，任何其他的NP问题都能够以多项式时间转化成它。结果是，如果一个NP完全问题实际上被证明是P问题（例如能够构造以多项式时间来解决哈密顿问题的一个确定论算法），那么接着还有是否所有的NP问题实际上都是P问题。否则，如果P≠NP，那么NP完全问题就不可能用确定论算法以多项式时间来解决。
显然，复杂性理论表达了图林机或图林类型机的算法能力的程度。它在科学应用和工业应用中具有实际的后果。但是，它是否意味着人的思维的极限呢？复杂性理论的基本问题（例如N＝NP或N≠NP）涉及到算法的速度、计算时间、存贮能力等等的度量。另一个问题是，人们如何开始发现复杂性程度不同的算法。这是计算机科学家的创造性工作，是算法的复杂性理论中不考虑的。
另一方面，哥德尔的著名定理常常被认为限制了计算机和人的思维的数学能力。他的不完全性定理说，对于形式数论的每一协调的公理化扩展，就有一个（封闭的）不确定的表达式。实际上，他的定理陈述了，在整数的真陈述在其逻辑内不可能得到证明的意义上，任何合理的协调的算术逻辑都是不完整的。甚至如果我们用不可确定的表达式来扩展我们的公理化，那么也会有另一表达式在扩展的形式化中是不可确定的。哥德尔的结果表明，在莱布尼茨和希尔伯特传统中对于完整协调的算术逻辑的形式化追求，是注定要失败的。
而且，哥德尔证明，算术逻辑——它可能是不完整的——使用可以在其逻辑内表示的方法来使之协调，也是不可能的。在哥德尔的著名结果提出来若干年以后，金藤（1909－1945）证明了初等数论的协调性，他运用了所谓的EO归纳法，该方法是通常的归纳法对自然数的无限扩展。但是，金藤的扩展的证明法的协调性却还是有疑问的，有待证明。换言之，证明方法的复杂性并不低于被证系统的复杂性。因此，只可能有相对协调的证明，所用证明方法必须得到证明，所用来进行证明的方法又需要得到证明，如此等等。对于人的思维，不存在绝对的可以由形式算法提供的协调性基础。
但是，哥德尔定理对人的思维的限制是有某些基本假设条件的：我们必须把定理的证明作为人的智能的关键。公理仅仅适用于这样的精神模型：它是由其中所有知识都仔细形式化了的机器构成的。而且，哥德尔定理仅仅是对协调机的限制，而模糊性、不协调性和迷惑性都是人的决策的典型特征。如果我们在作出是否要行动的决定之前先要作出长时间的仔细的定理证明，那么我们就不可能有长期的生存。还应该考虑到，图林机具有固定的数据结构，而人的精神则是对新奇经验开放的，并能够从错误中进行学习。因此，哥德尔定理对于机器的限制，就如同对于人的大脑封锁新信息的进入一样。
1936年，丘奇和图林证明了根本没有一种算法能决定一个一阶预测逻辑的表达式是否是同义反复的真理。随之即有，为找到某种数学证明，我们必须具有某些启发性思想。
所以，AI的第一阶段（1957…1962）是受启发性编程问题支配的，这意味着在可能的分支树中自动地寻求人的问题求解，其间借助启发性来控制和评价。一个例子是纽厄尔、肖和西蒙的“逻辑理论家”（1957），它首次对罗素和怀特海的《数学原理》中前面的38条定理提供了证明。他的启发性来自一些人在心理学测验中使用的约略估量法。
1962年，这些模拟程序被推广和扩展到所谓的“一般问题求解者”（GPS），它被假定为人的问题求解的启发性框架。但是GPS只可能解决形式化微观世界中的一些无意义的问题。另一个启发性编程的例子是，在博奕（下棋、将军）中寻求取胜策略。最初的模式识别程序（例如词语和符号的词汇表和句法表）都是以统计方法为基础的。但是从长远的观点看，这些早期的任何程序，都没有证明一般认知模拟程序中的欣快信念。至少，它的形而上学鼓舞了麦卡锡发明编程语言LISP，它是作为一种功能的编程语言引入的，用于处理可怕的符号表，成为今天基于知识的系统的一种最强大的编程语言。
在一般方法失败以后，AI研究者们传播了一种预设的“语法信息处理”程序。AI的第二阶段（1963－1967）以专业程序的发展为特点。这样的专业程序，例如有求解简单代数问题的STUDENT，进行类似物体的模式识别的ANALOGY，等等。麻省理工学院的马尔文·闵斯基是这个时期的头面人物，他放弃了进行心理学模拟的主张：“目前的探索，其特点是聪明地选取问题从而得到复杂智能活动的幻象来进行的预设求解。成功的实用编程方法依赖于专业知识，这个思想首次被加以强调，成为后来基于知识的系统的中心概念。
对于问题求解的一般原理的追求，在理论计算机科学中仍在继续：J．A．罗宾逊引入了所谓的以预测逻辑演算和赫布兰德的完全性定理为基础的求解原理，允许用逻辑反驳程序去发现证明。
在AI中推动实用和专业编程方法，在第三个阶段（1967－1972）得到了加速发展。其标志是构造出专业系统、知识表示方法和对于自然语言的兴趣。发明了在数学应用中取得成功的MACSYMA程序的J．摩西描述了AI中范式的变化：“事实上，1967年是我的精神的转折点，那时候我充分地感受到一般原理的旧思想必须放弃……并抓住了我称作专业技能至上的证据。”
这一时期的另一个著名例子是DENDRAL程序，它运用了质谱学中化学家的专业知识，以发现分子的结构式。这个阶段中的一个范式的例子变成了机器人的SHRDLU程序，机器人可以操纵不同组件组成的小世界。这种系统可以用英语理解和回答关于这个组件世界的问题，执行操作这个组件世界的指令，并把次序划分为一系列操作，理解干了什么并为什么这样干，并用英语描述它的行动。
在第四阶段（1972－1977），知识的描述、组织和处理成为了把工程学和AI哲学结合起来的中心范式。米彻尔·费根鲍姆引入了“知识工程”这一术语，用于所谓专家系统的发展。一个例子是用于医学诊断的MYCIN程序，它模拟了一个具有细菌感染专业医学知识的内科医生。
一种新的知识表示方法是马尔文·闵斯基提出的框架概念。一种用于符号性知识处理的新的编程语言是PROLOG（“逻辑编程”），它可以与LISP相比拟。
AI的第五阶段（1977－1986）被说成是托马斯·库恩的意义上的“常规”阶段，指的是专家系统范式正在运行并实现了商业化。一些工具发展起来，以建设诸如大规模汽车生产使用的新专家系统。AI正在从实验室和哲学家的研究中崛起，正在变成世界性的知识工业的关键性技术。
接下去，我们重点讨论专家系统，因为这里看来具有最令人感兴趣的哲学问题。一个专家系统是一种计算机程序，其中已经装入了知识和能力，使得它可以在专家水平上进行操作（例如化学中的DENDRAL和医学中的MYCIN）。人类专家的推理过程示意在图5．4中。
一些专家系统甚至可以揭示为何它们拒绝一定的推理途径而选择其他的途径。设计者们在努力工作以实现这一点，因为他们知道，专家系统的最终运用取决于它对于使用者的可信度。如果它的行为是透明的、可解释的，那么它的可信度就会增加。
但是，与人不一样，专家系统的知识是限于某种专业信息基础的，而没有关于世界的概括性、结构性知识。因此，专家系统在数字计算机的约定程序和人之间发挥着某种中间功能（图5．5）。
一个专家系统包括如下的组件：知识基础、问题求解组件（推理系统）、解释组件、知识获取组件和对话组件。它们的协调示意在图5．6中。
知识是专家系统运行中的关键性因素。知识具有两种类型：第一种类型是领域事实，它们书写在该领域的教科书和杂志中；对于一个领域的实践同样重要的是第二种知识，叫做启发性知识，是在该领域中的良好实践和进行判断的知识。正是实验性的知识，猜测高超艺术为一位专家经过多年工作所能获得的。
顺便说一下，知识库与数据库不同。例如，一位医生的数据库是关于病人的记录，包括病人历史、重要症状的测量、所开药物和药物反应。这些数据必定要通过医生的医学知识来解释，以进一步进行诊断并制订医治方案。知识库是医生在他的医学教育中和在实习阶段、高级训练阶段、专业训练阶段和医学实践中学会的东西。它包括事实、倾向、信念和启发性知识。
启发性知识是最难获得的，因为专家很少自觉地认识到它是什么。所以，跨学科训练的知识工程必须去获得专家的规则，将其表示为编程语言，并植入工作程序中。这个专家系统的组件叫做知识获取。它在专家系统的知识处理过程中的中心功能示意在图5．7中。
最重要的知识表示方法是产生系统、逻辑、框架和语法网络。除了知识以外，专家系统还需要一种推理程序，一种用以理解和作用于知识和问题数据及其组合的推理方法。这些程序是独立于特定的知识库的，是建立在多种哲学方法论基础上的，为此我们将在后面分析几个专家系统的例子。
专家系统的解释组件的任务是向使用者解释程序的步骤。问题“如何”也就是要对该系统导出的事实或断言进行解释；问题“何时”则是要求，指出一个系统的问题或秩序的前提。
对话组件处理专家系统与使用者的通信。自然语言的处理器当然可以使甚至未受过专门训练的使用者也容易接受。
从技术的观点看，专家系统的局限性是显然的。首先是知识表示问题。所论领域的知识如何表示为计算机记忆装置中的数据结构并为问题求解所接受？其次是知识利用问题。推理器应该如何设计？第三是知识获取问题。获得知识是如何可能的？这对于自动的问题求解是非常重要的，以使得计算机容易将人的专业知识转移到符号数据结构中。
专家系统的最后一个也是最重要的问题是哲学问题。如何将专家系统的专业知识库与关于世界的一般化结构化的知识结合起来？这种一般化结构化的知识会影响人的专家的决策和行动。
因此，当医生作出进行手术的决策时，还将考虑到有关病人的生活条件（家庭、工作等）的非对象性以及他对于生命的态度。特别是，例如在当今有关死亡尊严的争论中，对于生和死这种基本问题；医生的总体态度和见识也是融入到他的决策中的，尽管立法上在寻求建立一般的行为标准，但对此却是难以进行规范的。例如，在法律的专家系统中也表现出同样的问题。法官会置规范系统的自治性于不顾，最终将发现某种可能决策的正式范围，在此他将倾向于他自己关于生命和世界的观点。对于这种主观性影响，不要抱怨缺乏客观性，而是要看作一种作出更为人道的医学和裁决的机会。不过，对此并没有排除，未来的计算机科学应该去进一步地扩展以专家系统为基础知识，这种知识今天还是非常专业化的。当然，根本性的局限也是明显的，是专家系统的本质所导致。
专家系统是问题求解程序的技术实现。因此，实际上存在着的专家系统可以由特定的要解决的问题来进行分类。图5．8示意了专家系统最重要问题的类型。
输入问题类型输出
测量数据、症状等→分类或诊断→规则/模式的识别
约束→设计→满足性质的对象
初始态、目标态→计划→将初始态转变到目标态的行动顺序
初始态→模拟→未来的后�