P vs. NP 五十年：AI正在解决不可解问题（2）

Lance Fortnow | 编译 Don | 编辑 青暮

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的问题：我们可以将前者视为可有效计算，而将后者视为可有效检查的问题。

大家如果想更多的了解P和NP的问题，可以去看看2009年的综述论文，或者一些其他的科普书籍自行了解。也有一些比较偏正式的介绍工作，比如Michael Garey 和 David Johnson在1979年出版的书籍，他们的这本书对于想了解NP完全问题的读者来说一定不能错过：Garey, M. and Johnson, D. Computers and Intractability. A Guide to the Theory of NP-Completeness.W.H. Freeman and Company, New York, (1979).

（未完待续）