文章插图
P和NP问题一直是计算机领域的老大难问题，那么在近50年间，人们对这个问题有什么深入的研究呢？让我们在本文中深挖这个世纪难题。在1971年5月4日，伟大的计算机科学家和数学家Steve Cook就在他的论文《定理证明程序的复杂性 The Complexity of Theorem Proving Procedures》中首次向世界提出了P和NP的问题。在50年后的今天，世人仍然在试图解决这个计算机领域中最著名的问题。其实在12年前（2009年），我也曾经就该问题进行了一些讨论，大家可以看之前的《P与NP问题的现状》综述。文章地址：Fortnow, L. The status of the P versus NP problem. Commun. ACM 52, 9 (Sept. 2009), 78–86. https://doi.org/10.1145/1562164.1562186计算机理论在近些年并没有得到很大的发展。从2009年那篇文章发表以来，P与NP问题及其背后的理论并没有发生显著的变化，但计算世界确实发生了变化。比如说云计算，就推动了社交网络、智能手机、经济、金融科技、空间计算、在线教育等领域的飞速发展。更重要的是，云计算还帮助了数据科学和机器学习的崛起。在2009年，世界前10大科技公司中出现了一家独大的场面——微软公司独孤求败。但是截至2020年9月，市值前七名的公司分别是苹果、微软、亚马逊、Alphabet（谷歌）、阿里巴巴、Facebook和腾讯，彼此平分秋色。不光是大公司的变革明显，计算机人才的需求量也是如此。据统计，在2009到2020年间，美国的计算机科学专业毕业生的数量增加了三倍有余，但这还是无法满足市场上对该领域人才的需求量。P和NP的问题作为数学界和计算机界的一个难题来源已久，它被列入克莱数学研究所的千年难题之一。而且这个组织还为能够攻克该问题的研究人员提供了上百万美元的奖金悬赏。我会在文章的末尾用一些例子来解释P和NP问题，这虽然没能让我们从本质上对其有更多的认识，但是也能看出来P和NP的很多思考和成果推动了这个领域的研究和发展。如果有人问你，你能不能在微博上找到一些人，他们彼此之间都是朋友，这帮人的数量大概是300左右。你会怎么回答这个问题？假如你在一个社交平台企业工作，而且可以访问整个平台的数据库，也就是能看到每个人的好友列表，那你可以尝试遍历所有的300人群组，然后挨个儿看他们是否有相同的关注人群，如果是，则他们被称为一个团（Clique ）。但是这样算法的计算量太大，数量也太多了，通常无法全部遍历。你也可以耍耍小聪明，也就是从小的群组开始，然后慢慢的将这个小群组扩大，纳入那些彼此之间都是好友的人。当然实际做起来可能也有难度。其实从理论上来说，这个问题没有最好的解决方案，没有人知道到底存不存在比挨个遍历更好的解决方案。这个例子其实就是一个典型的P和NP的问题。NP代表了可以有效检验一个解的准确性的一类问题。比如当你知道有300个人可能构成一个团，你就可以快速的检验出由他们两两配对的44850对用户到底是不是都是彼此的好友。成团问题（clique problem）是一个NP问题。P则代表了可以有效找到解的问题。我们不知道这300个目标人群的问题是否也是具有P的可解性质。实际上，令人惊讶的是，成团问题具有“NP完全”的性质。也就是说，当且仅当P=NP时，我们才可以快速有效地解决成团问题。许多其他问题都具有NP完全的性质，比如3 Coloring问题（是否可以仅使用三种颜色对地图进行染色，然后让相邻的两个地块没有相同的颜色）、旅行商问题（通过城市列表找到最短路径，让这个旅行者能够在路径所有城市之后回到出发城市），等等。形式上来说，P代表“确定性多项式时间”，也就是可以在输入长度的多项式限定时间之内解决的一类问题。NP则代表“非确定性多项式时间”。在实际的算法开发中，我们最好可以换个角度看待P和NP的问题：我们可以将前者视为可有效计算，而将后者视为可有效检查的问题。
