计算机产生于对"可计算性”这个数学概念的一种理论研究，而这种理论研究比计算机技术早15年以上。1931年，奥地利数学家哥德尔的一项重大发现（不完备定理），引发了数学家对“可计算性”的研究。哥德尔的发现与希尔伯特提出的一项挑战有关（希尔伯特计划）。
19世纪，研究数学的公理化方法获得了成功，并成为当时的主流，这使希尔伯特大受激励。公理化方法是说，我们可以这样来开创一个数学分支∶先是构建一套基本假设——“公理”，然后从这套公理出发进行逻辑推导，从而产生出这个数学分支中的所有事实。这样，"真理"就化归为“能从公理出发而得到证明的东西”。这个数学观点最早是由古希腊数学家泰勒斯于公元前700年前后提出的，而且它形成了古希腊数学的基础。例如，欧几里得在他著作《原理》中，就是首先列出5 条基本公理，然后从这些公理出发推导出所有的定理来阐述几何学的。
在成功地为欧几里得几何构建了一套合适的公理之后，希尔伯特提出，对于数学的任何其他分支都能够“构建出”一套公理，这一想法后来被称为希尔伯特计划。希尔伯特希望在数学的任何领域，写出一套基本的假设（公理），而这个数学分支中的所有事实都可以由这套公理推出，这在理论上可行的。
1931年，哥德尔的不完备定理（不完全性定理）令整个数学界为之震惊。他的发现就是这个假设并不成立。他证明在数学的任何包含初等算术的部分中，不论你写出多少条公理，总是会存在一些正确的陈述无法从这些公理出发而得到证明。这彻底粉碎了希尔伯特计划。数学中的情形与生活中的情形一样，有一部分真理注定要永远保持让人难以捉摸的状态。
哥德尔把可证明性的问题转化成与之等价的关于某种从自然数到自然数的函数的可计算性的问题，从而证明了上述结果。
哥德尔证明，在任何公理化的系统中，总存在一些函数，它们在这个系统中是不可计算的。为此，他不得不建立了一种关于“可计算函数”概念的形式理论。
在哥德尔工作的基础上，其他一些数学家开始研究可计算性的概念，试图搞清楚到底哪些函数是可计算的，哪些不是。
数学家克林、图灵等人证明的定理，在理论上确立了制造“计算机”的可能性，这在计算机早期发展中起到了重大的作用。而那些从事这种理论研究的数学家（特别是图灵和冯·诺伊曼）在这种新技术的发展中则起到了举足轻重的作用。
从一开始，就有一些数学家对怎样用计算机来帮助解数学问题十分感兴趣，而且由于计算机技术而产生了许多新的数学分支——包括数值分析、逼近论、计算数论和动力系统理论。还有一些数学家，他们本着改进计算机计算方式的想法来研究计算的概念。一些这样的早期研究导致产生了计算机科学中的新学科，如形式语言理论、算法理论、数据库理论、人工智能和计算复杂性。正是在计算复杂性中，我们发现了一个千禧难题，其中的一位关键人物是库克（Stephen Cook）。
库克库克1939年出生于纽约州。1957年，库克进入密歇根大学，学习电机工程。大学第一年，库克选了一门计算机编程课程，并深深沉迷其中。他与一个朋友一起编写了一个检验哥德巴赫猜想的程序。20 世纪50年代，计算机科学还没有成为一门独立的学科，但是少数数学系开设了与计算机有关的课程。库克选修了密歇根大学开设的所有与计算机有关的课程。他对图灵对停机问题特别感兴趣。
1961年库克从密歇根大学毕业后，便去哈佛大学攻读数学博士学位。他原本计划研读代数学，但很快就发现自己已深受逻辑学家王浩的影响，当时王浩在哈佛大学应用科学部任教。王浩研究的是自动定理证明这个新领域，这个新学科被麦卡锡命名为人工智能。
在哈佛大学期间，库克还看到了拉宾（Michael Rabin）在复杂性理论方面的突破性研究工作。复杂性理论的任务是分析计算过程，看看这些计算过程执行起来可以达到怎样的有效程度。
1971年，库克发表了题为“定理证明过程的复杂性”的论文，其中介绍了他新发现的一个理论概念，称作NP完全性。接下来的事，都已载入史册了。由于这个发现，库克很快被选为加拿大皇家学会会员和美国国家科学院院士。
那么库克在1971年想出的这个NP完全性概念究竟是什么呢？
一个推销员设想你是一位推销员，你的大本营在A城市。你必须驾车去B、C和D这三个城市推销商品，从A出发，最后还要回到A。为了节省汽油和时间，明智的做法是，对你的行进路线作一番规划，使得你要走过的总路程尽可能地短。那么你要对这三个城市进行排序，你得到的将是如下结果，
你可以很容易地挑选出一条最佳路线。
但你要去10个城市推销呢。在这种情况下，向上面那样罗列出所有的路线似乎不现实，你需要用计算机来帮你。很快，计算机帮你计算出，要去10个城市推销，你一共有3628800种不同的路线可供选择。这里涉及阶乘计算，
