计算机产生于对"可计算性”这个数学概念的一种理论研究，而这种理论研究比计算机技术早15年以上。1931年，奥地利数学家哥德尔的一项重大发现（不完备定理），引发了数学家对“可计算性”的研究。哥德尔的发现与希尔伯特提出的一项挑战有关（希尔伯特计划）。

19世纪，研究数学的公理化方法获得了成功，并成为当时的主流，这使希尔伯特大受激励。公理化方法是说，我们可以这样来开创一个数学分支∶先是构建一套基本假设——“公理”，然后从这套公理出发进行逻辑推导，从而产生出这个数学分支中的所有事实。这样，"真理"就化归为“能从公理出发而得到证明的东西”。这个数学观点最早是由古希腊数学家泰勒斯于公元前700年前后提出的，而且它形成了古希腊数学的基础。例如，欧几里得在他著作《原理》中，就是首先列出5 条基本公理，然后从这些公理出发推导出所有的定理来阐述几何学的。

公理化方法的问题在于，如何“构建”公理，这并不容易。欧几里得的“平行”公设就引发了人们数百年的争论，这导致了数学家研究出各种“非欧几何”。直到19世纪后期，希尔伯特进行了一次严密的研究，一套完整的几何公理才得以建立起来。

在成功地为欧几里得几何构建了一套合适的公理之后，希尔伯特提出，对于数学的任何其他分支都能够“构建出”一套公理，这一想法后来被称为希尔伯特计划。希尔伯特希望在数学的任何领域，写出一套基本的假设（公理），而这个数学分支中的所有事实都可以由这套公理推出，这在理论上可行的。

1931年，哥德尔的不完备定理（不完全性定理）令整个数学界为之震惊。他的发现就是这个假设并不成立。他证明在数学的任何包含初等算术的部分中，不论你写出多少条公理，总是会存在一些正确的陈述无法从这些公理出发而得到证明。这彻底粉碎了希尔伯特计划。数学中的情形与生活中的情形一样，有一部分真理注定要永远保持让人难以捉摸的状态。

哥德尔把可证明性的问题转化成与之等价的关于某种从自然数到自然数的函数的可计算性的问题，从而证明了上述结果。

这就是为什么他的定理只适用于数学中那些包含某种算术的部分。这些公理得让人们可以做这种算术。

哥德尔证明，在任何公理化的系统中，总存在一些函数，它们在这个系统中是不可计算的。为此，他不得不建立了一种关于“可计算函数”概念的形式理论。

在哥德尔工作的基础上，其他一些数学家开始研究可计算性的概念，试图搞清楚到底哪些函数是可计算的，哪些不是。

注意，没有人关注实际的计算。也没有具体的数被涉及到。这是一项关于什么样的计算在原则上可以进行的纯理论研究。

数学家克林、图灵等人证明的定理，在理论上确立了制造“计算机”的可能性，这在计算机早期发展中起到了重大的作用。而那些从事这种理论研究的数学家（特别是图灵和冯·诺伊曼）在这种新技术的发展中则起到了举足轻重的作用。

从一开始，就有一些数学家对怎样用计算机来帮助解数学问题十分感兴趣，而且由于计算机技术而产生了许多新的数学分支——包括数值分析、逼近论、计算数论和动力系统理论。还有一些数学家，他们本着改进计算机计算方式的想法来研究计算的概念。一些这样的早期研究导致产生了计算机科学中的新学科，如形式语言理论、算法理论、数据库理论、人工智能和计算复杂性。正是在计算复杂性中，我们发现了一个千禧难题，其中的一位关键人物是库克（Stephen Cook）。

库克1939年出生于纽约州。1957年，库克进入密歇根大学，学习电机工程。大学第一年，库克选了一门计算机编程课程，并深深沉迷其中。他与一个朋友一起编写了一个检验哥德巴赫猜想的程序。20 世纪50年代，计算机科学还没有成为一门独立的学科，但是少数数学系开设了与计算机有关的课程。库克选修了密歇根大学开设的所有与计算机有关的课程。他对图灵对停机问题特别感兴趣。

图灵停机问题实说，即不存在这样一种程序，它能对任何给定的程序进行检查以判定这个程序是不是能在有限的时间内运行结束。

1961年库克从密歇根大学毕业后，便去哈佛大学攻读数学博士学位。他原本计划研读代数学，但很快就发现自己已深受逻辑学家王浩的影响，当时王浩在哈佛大学应用科学部任教。王浩研究的是自动定理证明这个新领域，这个新学科被麦卡锡命名为人工智能。

在哈佛大学期间，库克还看到了拉宾（Michael Rabin）在复杂性理论方面的突破性研究工作。复杂性理论的任务是分析计算过程，看看这些计算过程执行起来可以达到怎样的有效程度。

1971年，库克发表了题为“定理证明过程的复杂性”的论文，其中介绍了他新发现的一个理论概念，称作NP完全性。接下来的事，都已载入史册了。由于这个发现，库克很快被选为加拿大皇家学会会员和美国国家科学院院士。

那么库克在1971年想出的这个NP完全性概念究竟是什么呢？

设想你是一位推销员，你的大本营在A城市。你必须驾车去B、C和D这三个城市推销商品，从A出发，最后还要回到A。为了节省汽油和时间，明智的做法是，对你的行进路线作一番规划，使得你要走过的总路程尽可能地短。那么你要对这三个城市进行排序，你得到的将是如下结果，

你可以很容易地挑选出一条最佳路线。

但你要去10个城市推销呢。在这种情况下，向上面那样罗列出所有的路线似乎不现实，你需要用计算机来帮你。很快，计算机帮你计算出，要去10个城市推销，你一共有3628800种不同的路线可供选择。这里涉及阶乘计算，

仅仅是10个城市，就有这么多的路线。但由于阶乘数增长得如此之快，还没增加几个城市，计算机也不堪重负了。例如，

数学家把以这种方式增长的数学模式称为呈指数增长。阶乘数以指数增长。

列出所有的可能性并对它们进行比较，以找出最短的路线，这是解决这个问题的一个非常天真的方法。还有一个更好的方法吗？因为推销员问题在工业和商业上十分重要，所以数学家使出浑身解数试图找到其他的方法。他们的方法可归为两类，这两类都涉及高深的数学。

一种方法是寻求近似解。我们不是去寻找一条总路程最小的路线，而是去寻找一条与最佳路线的长度偏差落在（比方说）5%以内的路线。

另一种方法是寻求一个准确的答案，但要全面观察这些城市的地理情况，并设法利用这些城市的布局特点，以减少可能路线的数目。但这种方法有个明显的缺点，就是你得到的答案只适用于一组特定的情况。增加或减少一个城市，就得重头再来。

1998年，一个数学家团队找到了巡访美国所有人口在500以上的13509个城市的最短路线。他们用由32台奔腾PC机支持的三台高性能多处理器科学计算机联成一个网络，并在这个网络上进行了三个半月的运算。

然而，如果不考虑近似解，不考虑对一些特定的城市组合求解，那么就没有人知道推销员问题的实用解答。

推销员问题是20世纪30年代由维也纳数学家门格首次提出的。此后不久，数学家在工业和管理中发现了同样重要的其他问题，而且同样也不能解决。

例如，有一个过程调度问题。在这个问题中，你面对着许多工作，它们都必须完成，比方说在工厂中就会遇到这样的情况。这些工作中有一些要在另一些工作完成之后才能做，而有一些则是能独立完成的。你能不能把这些工作分成组，使得完成所有这些工作时间最少。每一组中的工作将被视作一个过程，即完成其中的一个工作后才能做其中的下一个工作，但各个过程可以同时进行。

现代的汽车制造就是一个很好的例子。在组装车身的同时可以组装发动机，但组装发动机的各项工作必须按照一个特定的顺序进行。

与推销员问题一样，一旦你将这些工作分了组，使得每组工作可以与所有其他组同时进行，那么计算总时间所用的数学便是小菜一碟。你所要做的只是在每组中将完成各项工作的时间加起来，然后在这些时间中找出一个最长的。这个最长的时间就是用这种特定的分组法来完成所有工作所需的时间。问题是为了求出所需时间最少的调度安排，你必须对所有可能的分组都进行这样的计算，而就像推销员问题中可能路线的数目一样，这个可能分组方式的数目随着工序的增长而以指数增长。

当纯粹数学家开始思考这个问题时，他们会问一个非常与众不同的问题。他们说，假设推销员问题根本不存在有效的解法（不考虑近似方法）。那么这个问题就变成，你能证明吗？如果能，那么你至少知道花费大量的时间和计算资源来试图解决它是没有意义的。

要令人信服地证明试图解决这个问题是浪费时间和精力，你必须给出一个扎实可靠的证明，证明不存在明显好于蛮力法（即对所有的可能性进行试验）的方法可以解决这个问题。

理论工作者首先面对的一个问题是，找出一种方法来度量在一台计算机上执行一项特定任务需要多长时间。以推销员问题为例，答案（至少）依赖两样东西∶所使用的计算机和城市的数量。从理论上讲，计算机不是一个重要的因素，关键在于城市的数量。

很明显，一个问题所涉及的数据越多，花费在计算上的时间也越长。但是长出多少呢？准确地说，如果数据总量增加了一个确定的数量，计算时间会增加多少呢？例如，如果我们将数据总量翻一番，计算时间是不是也会翻一番？

既然我们关心的是计算时间的相应增长，那么不管是两倍、三倍还是更多，实际上的计算时间是多少是无关紧要的。在这种情况下，我们需要做的只是弄清楚这个计算所涉及的基本步骤有多少。这就把问题从度量时间转化为对基本步骤计数了。

什么是一个基本步骤？以算术为例，一个基本步骤就是将两个单独的数相加或相乘。算上进位，把两个N位数相加至多涉及3N个基本步骤。例如，将两个4位数相加需要3×4=12个基本步骤。

把两个N位数相乘的标准方法涉及N^2个基本的整数对乘法，最多再加上处理进位的N个加法。一共最多有N^2＋N个基本运算。注意到表达式N^2＋N的值总是小于N^2＋N^2，即2N^2。于是，两个N位数相乘所涉及的基本运算少于2N^2个。

加法就是所谓"线性时间过程”的一个例子。一个线性时间过程是对规模为N的数据，至多需要C×N个基本步骤来完成的过程，这里C是某个固定的数（在心算加法的情况中，C=3）。

既然我们只是同意用基本步骤来进行分析，而不是用计算时间进行分析，我们或许应该称之为“线性基本步骤”而不是“线性时间”。但是由于这类分析的原本目的是要了解计算机执行一个特定任务需要花多少时间，所以最初采用了“线性时间”，这就固定了下来。

我们可以假定，任何基本运算都需要相同的固定时间，那么基本步骤的数目就直接对应于计算所花的时间。

词组“线性时间”中的“线性”是指，如果你画出步骤数目与数据规模之间关系的图像，那将是一条直线。（直线的方程式将是S=CN，S是步骤数目。）

相应地，乘法是一个"平方时间"过程。一般来说，如果一个过程对规模为N的数据至多需要C×N^2个步骤来完成，其中C是某个固定的数，那么它就被说成是以平方时间运行。

一个比线性时间过程和平方时间过程更为一般的概念是“多项式时间过程”，一个多项式时间过程是对规模为N的数据至多需要C×N^k个基本运算的过程，其中C和k是某两个固定的数。

所有的算术四则运算（加、减、乘、除）都是多项式时间过程。

当面对一个计算过程时，理论工作者就寻找这样一个代数表达式（例如CN、CN^2或CN^k），它能给出这一过程对于规模已知为N的数据来说，所需要的基本步骤数目的一个上界估计。他们称这样的表达式为这个过程的"时间复杂性函数"。多项式时间过程是以多项式表达式为时间复杂性函数的过程。

大致而言，多项式时间过程是计算机能有效处理的一种过程。如果那两个固定的数C和k都十分巨大，那么计算时间可达数亿年。不过在实际上，日常生活中往往会产生的多项式时间过程所具有的C和k的值是完全适度的，k一般是个一位数，因此它们确实能被计算机有效地处理。

还有一个类型称为“指数时间过程”，当数据规模为N时，需要2^N个基本步骤来完成的过程（底数也可以是某个大于2的数）。

指数时间过程几乎无法在计算机上运行，因为随着N的增大，步骤增加速度太快。如果在一个国际象棋盘上以2^N的规律放硬币，那么最后一格硬币的高度能一直伸到半人马座的比邻星（37万亿千米）。

对于在工业和商业中产生的几乎所有的指数时间过程，即使要处理规模相当适度的数据，也要让世界上最快的计算机花上比宇宙寿命还要长的时间。

显而易见，如果对于一个特定的问题，你所知道的唯一解决方法是使用指数时间过程，那么你将不可能解决这个问题，除非数据规模非常小。

多项式时间过程与指数时间过程之间的鸿沟也说明了这种分类的一个明显缺点∶它太过粗略了。数学家意识到了这一点后，便寻找中间尺度的过程复杂性。他们注意到，对于像求解推销员问题的过程来说，困难并不是由于复杂的计算。使得问题几乎无法解决的原因，是需要检查的可能性的数量之多，使得完成全部过程所需要的时间长得令人绝望。

为了试图把这种过程与一种真正复杂计算的过程区分出来，数学家提出了第三种类型∶非确定性多项式时间过程，或简称NP过程。由于通常的计算机都是确定性的，所以采用“非确定性”这个词会给人们一个暗示，即这个新概念是一个理论的东西，与实际的计算基本无关。下面是它的大致思想。

设想你有一台这样的计算机，它能在一次计算的某些阶段从许多备选的数中作出一个完全随机的选择。比方说，当面对推销员问题的一个具体例子的时候，这台计算机能从这位推销员可以走的所有可能的路线中随机地选出一条。为了解出这个问题，这台计算机选出一条路线并算出相应的总距离。这条选出的路线不是最短路线的概率是极大的。但假定这台特别的计算机具有好得不可思议的运气，使得它总是作出最佳的选择。于是它会在多项式时间内解决这个问题。作出一个随机猜测并能幸运地猜中的本领，使得我们避开了可能性的数量大得令人绝望这个难题。

一般说来，如果一个问题或任务可以用一台非确定性计算机在多项式时间内解出或完成，我们就说它是NP型的，而非确定性计算机就是能从一系列备选对象中作出一个随机选择而且能极其幸运地选中的计算机。

但要注意的是，这种计算机必须要检验它的猜测的正确性。NP类的本质在于，仅仅是可能性的巨大数量造成了困难。对于一个NP问题，检验一个给定的答案是否正确这件事必须是能在多项式时间内完成的。

从直觉上说，NP问题介于多项式时间问题（简称P问题）与指数时间问题之间。因为NP概念建立在一个完全不现实的想法上，即有一种计算机能老是作出最佳的随机选择，所以它是纯理论的。然而它显示出相当大的重要性。一个理由是，在工业和管理中出现的大多数指数时间问题都是NP型的。使得它们很难解决的原因并不是有关的计算很复杂，而是必须对极其大量的实质上相同的情况重复执行一种相对容易的计算。

当NP分类于20世纪60年代第一次被提出时，计算机科学家臆断P类与NP类并不是同一个类——虽然每个P问题当然都是NP问题，但是有一些NP问题肯定不属于P类。理由是，看来一台运行多项式时间算法的标准计算机无论如何也不可能表现得像一台想象的非确定性计算机作准确猜测时那样。例如，专家们认为，如果没有一台假想的非确定性计算机的准确猜测能力，推销员问题也许根本不可能在多项式时间内解决。

人人都认为这只是个时间问题∶迟早有人会给出某个可证明不属于P类的NP问题——不是推销员问题，就是其他什么问题——从而证明P和NP是不同的问题类。但这件事至今没有发生。也没有人能证明相反的结论。于是，P对NP问题产生了。

20世纪60年代后期，这个问题已相当重要。工业与管理中的许多重要问题都被证实是NP问题。如果能证明P就是NP，那无疑将激发人们以极大的努力去找出解决这些重要问题的有效过程。

我应该指出，证明了NP与P相同，这本身并不能导致人们得出解决具体的NP问题的有效过程。它表明的只是任何NP问题在原则上可用一个多项式时间过程解决。关于这样的一个过程可能是什么样的，它不一定会提供什么线索。

这时，库克登场了。库克证明存在一个特殊的NP问题，它具有一种奇特的性质∶如果这个特殊的问题能用多项式时间过程解决，那么其他任何的NP问题也能。这是一个关于什么类型的任务可以在一台非确定性计算机上执行的问题。

库克证明其结论的方法是∶他显示了怎样可以将任意给出的NP问题转化成他这个特殊的问题，这样，如果他这个问题能在多项式时间内解决，那么通过转换，那个给出的NP问题也能。库克将这个性质命名为NP完全性。根据库克的定义，对于一个NP问题，如果发现了一个可以解决它的多项式时间过程将意味着，NP类中的每一个问题都可以用一个多项式时间过程解决，则这个NP问题被称为NP完全的。

虽然库克的问题是一个来自形式逻辑的高度理论性的问题，但没过多久，卡普等人就证明了其他许多更为令人熟悉的NP问题也具有这个NP完全性，其中包括推销员问题。

对工业界人士而言，发现能解决诸如推销员问题的有效过程就意味着利润大幅增长。这并不是说NP完全性就意味着一个问题肯定不能有效地解决。准确点说，证明一个特定的问题是NP 完全的，就对它的难度，以及你将找到一个多项式时间过程来解决它的不可能程度给出了一个尺度。下面解释一下。

现在假设你发现你的NP问题事实上是NP完全的。那么大多数专家就把此作为一个不值得花费时间和精力来为它寻找一个完整解的充足理由。他们转而把自己的精力用在寻找一个好的近似通解上。因此，尽管NP分类具有高度的人为性质，但它的确有助于管理者决定把他们的研究精力投在什么地方。

但是未被解决的P对NP问题依然潜伏在每一件事情后面。一个关于P与NP相同的证明将在原则上使得关于NP 完全性的所有研究都变得徒劳。这样的证明还会对互联网的安全产生严重的后果。因为破译RSA密码是一个NP问题。人们还不知道RSA加密系统的破译问题是不是NP完全的（很可能不是），因此，用不着证明P与NP相同，也许就会研究出这个问题的一个多项式时间解法。而另一方面，如果证明了P与NP相同，那么立即就说明RSA系统的破译问题可以在多项式时间内解决。那样的话，整个互联网的安全系统将处于极不可靠的状态。

P与NP是相同还是不同？发现有许多问题是NP完全的，就意味着数学家有许多种方法来试图证明P=NP。无论哪一个NP完全问题，只要找到一个能解决它的多项式时间过程，那么就立即得到P=NP。例如，一个解决推销员问题的多项式时间过程，就是关于P=NP的一个证明。

不过，要证明P与NP不同，你必须去找一个你能证明不存在多项式时间过程解法的NP问题。这个问题可以是一个已知的问题。例如，如果你能证明推销员问题肯定无法用多项式时间过程解决，那么你就证明了P与NP并不相同。

这并不像你想的那样简单。取某个能解决推销员问题的特殊过程并且证明它不是多项式时间过程，这是不够的。证明迄今研究出的所有过程没有一个是以多项式时间运行，也是不够的。确切地说，你必须证明不可能存在以多项式时间解决这个问题的过程。这意味着你的证明必须考虑可以解决这个问题的任何过程，不仅仅是那些已知的，还要包括将来可能发现的任何过程。

在圈外人看来这也许有些奇怪，但是数学家已在某些情况下能证明关于这种未知的对象集合的结果。库克对NP完全性的证明就是这样一种结果。他证明了如果他那个特殊的NP问题可以在多项式时间内解决，那么包括所有尚未发现的NP问题在内的任何其他NP问题都同样可以在多项式时间内解决。然而，在证明P≠NP的情况中，没人能证明存在某个NP问题，它无法用多项式时间过程求解。这就是P对NP问题为什么会成为一个千禧难题。