2. 为什么要讨论P和NP问题
在1971年的那个星期二的下午，Cook在ACM计算理论研讨会上发表他那篇关于NP完全的论文时，他证明了可满足性是NP完全的，而重言式是NP难的。论文中也推断说Tautology是不具备P特性的一个问题，当然，当时没有对这个问题进行很好的证明。但无论如何，这篇论文以及其中的证明方法，标志着复杂性理论的重大突破。
想要去证明一个数学概念通常具有很大挑战。算法和证明的基础概念至少可以追溯到古希腊时期，当然，他们从来没考虑过NP和P这样的问题。高效计算和非确定性的理论基础是在1960年代才发展起来的。但P和NP的问题在这之前很久就已经被提出来了，只是我们没有给它们正式冠名而已。
库尔特·哥德尔在1956年曾经写过一封给冯·诺依曼的信。在信中他就初步描述了P和NP问题。这封信直到1988年才被发现，并广为流传。
Richard Karp真正意义上首次将P和NP问题引入大家视野。他在1972年的论文中介绍了该问题，并随后得到广泛的关注。
我们知道很多有名的组合问题都是NP完全的，包括Clique, 3-coloring和旅行商问题。1973年，当时在俄罗斯的Leonid Levin在他两年前独立研究结果的基础上发表了一篇新的论文，并在这篇论文中定义了P和NP问题。当Levin的论文传播到西方的时候，P和NP问题也已经确立了作为计算领域最重要问题的地位。
（未完待续）
No post found!
为了方便大家，我们特此分享一些来自公共平台的文章供大家阅读。这些文章仅供参考，不代表本站编辑的观点、立场和态度。这些文章中的一切内容版权皆属于原作者或原平台。若涉侵权请予以告知，我们将尽快删除相关内容。谢谢！
Latest posts by 文章转载 (see all)
- 《纽约客》丨纪念9·11二十五周年 - 09/12/26
- 数学500年：新的黄金时代？（1） - 06/05/26
- 没有美洲，我们吃啥？ - 05/17/26