2000年的时候，克莱数学研究所公布了七个数学题，这七个数学难题，每解决一个，就可以发100万美元的奖金。这可以说是有史以来最难赚的100万美元。这七道数学题目分别是……算了，我说了你也做不出来。所以就说了，你只需要知道，这七道题中，只有一道叫庞加莱猜想的被证明了，现在奖金池里还剩下600万美元，所以，大家要加油啊。
证明庞加莱猜想的那个科学家叫格里戈里·佩雷尔曼，这家伙虽然很穷，但是他没有去领取那100万美元，而是跟他妈妈生活在一起，靠老妈的退休金生活。所以，我无话可说。
其中有一个定理叫P≠NP，这个定理是这七个数学题中最晚提出的，一度被认为是这七道题中最早解决的，但是，至今没解决。前些年，HP公司有个家伙说他解决了这个问题，并且写了1000页论文，结果被证实有严重的错误。
那这个定理跟本期图灵奖得主有什么关系呢？他简化了P≠NP定理的证明过程。因为我曾经对那100万美元非常痴迷，所以，我曾经花了大量的业余时间研究P≠NP定理，所以，我试图花些篇幅来解释这是一个什么问题。如果你因为听我这期节目，对P≠NP产生了深厚的兴趣，并且获得了100万美元的奖金，我相信你一定像佩雷尔曼一样对金钱不感兴趣，那么，请委屈一下，你把那些奖金领回来，然后送给我好不好？咱们就这样一言为定了。
我尽量用简单的语言解释我理解的P≠NP定理是什么东西。
P代表一类问题，这类问题是一类比较容易解决的问题，比如，把英文单词按照字母表顺序排列起来，或者把魔方还原，这些问题可以在确定性多项式时间内（即时间复杂度为多项式级别）解决。换句话说，这些问题可以由一个算法在多项式时间内解决。P类问题被认为是“易于解决”的问题。
NP类问题则不同，数独是典型的NP类问题。当给我一个答案的时候，我只能说我可以在多项式时间内验证这个答案是不是正确的，但是，我不保证我可以在多项式时间内找到这个解。比如，你有一个100×100的数独，我相信你无法快速的给出答案。但是，只要有了答案，我还是可以比较迅速的判断出，这个答案是不是正确的。
总结一下就是P类问题容易解决，也容易验证。NP类问题，容易验证，但是不一定容易解决。所以P类问题是NP类问题的子集。如果你能找到一个方法，让NP类问题也变成容易解决，也容易验证，那么，你就解决了世纪难题。你可以解决3×3的数独，再用点心就可以解决4×4的数独，你能找到一个方法很快的解决999 x 999的数独么？
显然这非常困难，但是P与NP能不能等价，现在没人证明。大部分科学家认为P≠NP，我也是这么认为的，但是，现在没有科学家给出确切的答案。在1930年以前，那时候的科学家非常自信，希尔伯特一句口号是：我们必须知道，我们终会知道。但是仅过了一年，哥德尔推翻的数学的基础，他证明，没有任何数学理论能证明其自身的一致性。
这对数学家的打击还是挺大的，让大部分数学家放弃了完备性的证明，转而先识别出哪些数学是可证明的，哪些是不可证明的，这样，只需要证明可证明的那些，不可证明的那些，就不浪费时间了。这里的先驱不得不再次提到图灵，他的工作是如何把数学问题分为可解决的与不可解决的。
这时，不得不提一下NP问题的另一个经典例子，哈密顿路径。哈密顿路径（Hamiltonian Path）是一种路径，路径上的每个顶点恰好访问一次。这一概念以数学家威廉·罗恩·哈密顿命名。若一个路径能从图中的任意一点出发，经过所有顶点，且每个顶点仅访问一次，则该路径为哈密顿路径。如果这种路径形成一个闭合环（起点和终点是同一个顶点），则称为哈密顿回路或哈密顿环（Hamiltonian Cycle）。
哈密顿路径的判定问题属于NP完全问题，这意味着没有已知的多项式时间算法可以解决所有图的哈密顿路径判定问题。
如果你找到了这样一条路径，则可以很快的验证是不是正确的，你拿根笔，把线连接起来，只要任意一点都没漏，也没有重复，就证明你是对的。但是要找到这样一条路径，则要困难的多。用复杂性理论专家Russell Impaggliazzo的话来说，合理的时间，其实是指宇宙终结之前。这个教授是加州大学的，他在网上有上课的视频，研究生的算法课，推荐想挑战自我的人去听一下。
还有一个叫欧拉路径的，两者看起来差不多，但是欧拉路径是P类问题，而哈密顿路径是NP类问题。欧拉路径（Eulerian Path）是指一条路径，该路径经过图中的每一条边恰好一次。如果这样的路径起点和终点是同一个顶点，则称为欧拉回路（Eulerian Circuit）或欧拉环。欧拉我就不多做解释了，欧拉（Leonhard Euler）在数学上的地位跟艾萨克·牛顿（Isaac Newton）在物理学上的地位是一样的。如果说爱因斯坦可以勉强跟牛顿齐名，那至今为止，还没有人可以在数学上跟欧拉齐名，数学家高斯可能是接近他的人。
没有人理解为什么这两个问题如此相似，但一个是P问题，一个是NP问题，为什么会是这样呢？这时候，本次电台的主人公Stephen Cook说，我懂为什么不一样。当时他在美国呆着非常的不爽，就搬家去了加拿大，到多伦多大学当老师。他花了一年的时间，就解决了这个问题。他发现，对于特定的NP问题，如果存在一个多项式算法可以解决这个问题，那么也可以解决NP中的其它所有问题。
他的这个理论，将NP问题进行了分类，他发现，几乎所有已知多项式算法的NP问题，最后都可以归纳为一个相同的问题，他将其称为NP完全问题。这意味着，只要解决其中一个问题，所有同一类的NP问题都将统一解决。当时，这个结论一发布，NP问题转化成了归类问题，大家都认为NP问题就要解决了。实际情况是，快60年了，这个问题仍然没有答案。
接下来，就来讲讲Cook的生平了，因为再讲深了，我也不懂，我只是懂一点皮毛而已。不过，按照的我观察，我还是认为NP问题就要解决了，算是那六个剩下问题中，最活跃的一个问题，大量的人类高智商大脑，就在研究NP问题。
1939年12月14日，库克出生于纽约州布法罗（Buffalo）。他的父亲是一名化学家，在著名的联合碳化物公司工作，并在布法罗大学任教，收入颇丰。然而，库克的父亲更喜欢乡村的恬静生活和清新空气，因此在库克10岁时，全家迁居到纽约州克拉伦斯的一个奶牛场。在那里，年轻的库克与牛羊为伴，还学会了挤奶。在乡村中学，库克的数学成绩优异，但当时他并未梦想成为数学家。他另一个爱好是下棋，这帮助他发展了逻辑思维能力。
在克拉伦斯，当地出现了一位传奇英雄——威尔逊·格莱特巴赫（Wilson Greatbatch），他发明了可植入式心脏起搏器，挽救了无数人的生命，声名远扬。库克对这位发明家非常敬仰和崇拜，暑假时曾在他手下打工，帮忙焊接晶体管电路板。当时，晶体管刚问世，是一项新奇的技术，库克对此也很感兴趣，并萌生了成为电气工程师的愿望。
1957年中学毕业后，库克离开克拉伦斯，前往密歇根大学学习科学工程。在大一时，他选修了一门新开设的课程——程序设计，第一次接触到计算机。作为作业，他编写了一个Algol程序，以验证哥德巴赫猜想，证明在机器允许的范围内，每个大于3的偶数都是两个素数之和。这使库克开始对计算机科学产生了浓厚的兴趣。
1961年库克获得学士学位后，转入哈佛大学研究生院深造，并在第二年取得了理科硕士学位。接着，他开始攻读数学博士学位，最初计划研究代数学。然而，他在哈佛遇到了一些对他影响深远的教师，改变了他的兴趣和方向。
首先，哈佛大学研究生院非常重视新兴学科的发展。尽管计算复杂性理论在当时仍处于萌芽阶段，学校还是邀请了一些这一领域的先驱和奠基人前来讲学或作报告，其中包括1976年图灵奖获得者拉宾（M. Rabin）、1993年图灵奖获得者哈特马尼斯（J. Hartmanis）和斯坦恩斯（R. Stearns）等人。库克对他们研究的问题产生了浓厚的兴趣，并决定将自己的研究方向转向计算复杂性理论。
库克的博士论文《论乘法的最小计算时间》（On the Minimum Computation Time for Multiplication）是他在这一领域的初步尝试。然而，该课题的局限性较大，难以从中找出一般规律。这时，哈佛大学应用科学研究所的美籍华人学者王浩的研究工作引起了库克的注意，并启发了他。后来，王浩成了他的导师。王浩是国际知名的数理逻辑专家和计算机科学家，他的研究对库克产生了重要影响。我曾经专门做过一期电台，专门讲王浩的。有兴趣的，可以找来听听。
他曾深入研究图灵和计算理论，并提出了一种图灵机的变形，称为B机器（Bmachine）。B机器仅有4条指令，且不允许自我修改，即不能擦除带上的记号。相较于图灵机，B机器更接近实际机器的运作方式，其能计算的函数正好是部分递归函数。
同时期，王浩致力于研究自动定理证明，即让计算机自行证明定理，特别是证明谓词演算中的定理，这涉及可满足性问题（Satisfiability），即判断给定的公式是否存在真假值的赋值使其成立。图灵早已证明一般谓词演算公式的可满足性问题在计算上是不可解的。
王浩的研究给了库克极大的启发，他意识到自动定理证明是研究计算复杂性问题的良好切入点。然而，谓词演算涉及个体与群体，并含有量词（全称量词”∀”和存在量词”∃”），使得研究变得复杂。于是，库克转向比较简单的命题演算公式的自动证明，获得了成功。1971年5月，他在俄亥俄州 Shaker Heights举行的第三届计算理论研讨会上发表了著名论文：“定理证明过程的复杂性”（The Complexity of Theorem Proving Procedures）。在这篇论文中，库克首次明确提出了NP完全性问题，并奠定了NP完全性理论的基础。NP完全性问题指的是在P = NP问题难以解决的情况下，库克从NP类问题中分出复杂性最高的一个子类，称为NP完全类。
库克证明了一个重要结论：对于任意选取的NP类问题和NP完全类问题，都存在一个确定性图灵机上的多项式时间复杂性算法，可以将前者转化为后者。这意味着，只要能证明NP完全类中的一个问题属于P类，就等于证明了NP类中的所有问题都是P类的，也就是说，P=NP。这一发现为研究P=NP问题的科学家们指明了一条道路和方向，不再需要盲目地进行探索。尽管科学家们仍在努力沿着库克所指示的路径前进，但至今仍未达到解决问题的光辉终点（P≠NP问题仍然没有明确答案）。然而，学术界一致认为，库克的NP完全性理论对计算复杂性理论作出了重大贡献。
库克的论文仅证明了命题演算的可满足性问题是NP完全的。然而，这一发现激发了卡普（R. Kap，1985年图灵奖获得者）等学者的研究兴趣。在库克的启发下，卡普等学者在随后的一年证明了关于组合优化的21个问题也是NP完全的，从而进一步加强和发展了NP完全性理论。
目前，他已经84岁了，在加拿大生活。他于1982年获得了图灵奖，还有一大堆其它的奖，我就不再一一赘述了。
我来冒个泡，科学上网，支持栋哥
谢谢