Lance Fortnow | 编译 Don | 编辑 青暮
P和NP问题一直是计算机领域的老大难问题，那么在近50年间，人们对这个问题有什么深入的研究呢？让我们在本文中深挖这个世纪难题。
在1971年5月4日，伟大的计算机科学家和数学家Steve Cook就在他的论文《定理证明程序的复杂性 The Complexity of Theorem Proving Procedures》中首次向世界提出了P和NP的问题。在50年后的今天，世人仍然在试图解决这个计算机领域中最著名的问题。其实在12年前（2009年），我也曾经就该问题进行了一些讨论，大家可以看之前的《P与NP问题的现状》综述。
计算机理论在近些年并没有得到很大的发展。从2009年那篇文章发表以来，P与NP问题及其背后的理论并没有发生显著的变化，但计算世界确实发生了变化。比如说云计算，就推动了社交网络、智能手机、经济、金融科技、空间计算、在线教育等领域的飞速发展。更重要的是，云计算还帮助了数据科学和机器学习的崛起。
在2009年，世界前10大科技公司中出现了一家独大的场面——微软公司独孤求败。但是截至2020年9月，市值前七名的公司分别是苹果、微软、亚马逊、Alphabet（谷歌）、阿里巴巴、Facebook和腾讯，彼此平分秋色。不光是大公司的变革明显，计算机人才的需求量也是如此。据统计，在2009到2020年间，美国的计算机科学专业毕业生的数量增加了三倍有余，但这还是无法满足市场上对该领域人才的需求量。
P和NP的问题作为数学界和计算机界的一个难题来源已久，它被列入克莱数学研究所的千年难题之一。而且这个组织还为能够攻克该问题的研究人员提供了上百万美元的奖金悬赏。我会在文章的末尾用一些例子来解释P和NP问题，这虽然没能让我们从本质上对其有更多的认识，但是也能看出来P和NP的很多思考和成果推动了这个领域的研究和发展。
（未完待续）
No post found!
- 《纽约客》丨纪念9·11二十五周年 - 09/12/26
- 数学500年：新的黄金时代？（1） - 06/05/26
- 没有美洲，我们吃啥？ - 05/17/26