2020年/02月/23日
P / NP
本文摘录自《可能与不可能的边界》
我本人对P/NP问题得到解决的前景持悲观态度：我认为P≠NP，而且此生都看不到它的证明。我们不会见证第2章中美妙世界的到来，但是也不能排除其可能性。我认为P/NP问题在未来的几个世纪内仍将是一个未解之谜。P/NP问题不仅仅是一个数学上的异类。虽然我们不能直接解决它，但研究它的过程赋予了我们一种通用的框架，有助于思考如何应对从实际需求中产生的那些困难的问题。今天人们在计算学方面面临哪些重大挑战？
并行计算：曾经每过18到24个月，计算机的计算速度就提高一倍，但现在我们正在触及物理极限，将来很难制造出比现在快得多的处理器。另一方面，计算机正在横向扩张，可以让多个处理器一起工作，不论是在同一块芯片上，还是在云端。如何调整我们的算法，以适应这个日趋并行化的世界呢？
大数据：从互联网到科学实验再到仿真研究，我们每天都在生成海量的数据。如何试图理解、感受、学习如此庞杂的信息，并形成预测能力？
一切事物的网络化：世界上大部分地区都有计算机网络，无论人们使用的是像Facebook这样的社交网络，或者仅仅通过电子邮件交流。很快几乎所有人造的物品都将成为这张大网的一部分，从我们穿的衣服，到阅读时提供照明的灯泡。我们如何更好地利用这个超级互连的世界？
无论最终的答案是P=NP还是P≠NP，对这一问题的研究过程本身都将在很大程度上影响我们应对这些挑战的方式。
证明P≠NP并非易事。你需要证明不存在有效的算法能解决团问题或任何其他的NP完全问题，这些算法既包括现有的也包括将来发明的。如何证明每一个潜在的算法都必将失败？人们相信这样的证明总有一天会出现，但有可能需要过上20年，200年，甚至2000年。
总有一天，当人们发展出的新技术最终能证实P≠NP的时候，数学家们会兴高采烈，为一个伟大的问题得到一个伟大的解答而欢呼。而求解P/NP问题过程中产生的技术将让我们深刻认识高效能计算的威力，这种东西会渗透到社会生活的方方面面。P/NP问题远远不只是一个数学谜题那么简单。它是一种思考的方法，一种根据问题的内在难度对其进行分类和认识的方法。
虽然尚没有P≠NP的确凿证据，我们起码知道了：当面临一个NP完全问题时，不可能找到一个在所有情况下都能解决该问题的算法。这时就需要借助于其他的工具，如近似计算、启发式方法、暴力破解等方法的组合，然后尽我们所能地争取最好的结果。NP完全性理论给了我们一个通用的思考框架，允许我们建立一套由很多技术组成的工具体系，向那些难以计算的问题发起有效的攻击。
P/NP问题让学术界团结在一起。物理学、生物学、经济学以及其他许多领域中都有NP完全问题的身影。虽然物理学家和经济学家所关注的问题有很大的差异，但这两类问题也存在着共性。所以分享各自的工具和技术将为双方都带来巨大的好处。例如，物理学中为了寻找物理系统的基态而开发的工具，对于经济学中寻找复杂经济环境中可能出现的均衡行为也是有帮助的。P/NP问题内在的难度同样促进了新技术的发展。
当代密码学家从P/NP问题受到启发，把密码学操作过程从一门艺术变成了科学。对于解决P/NP问题的强烈需求也在激励人们建造更快、更强的计算系统，催生了诸如量子计算这样的新技术。计算是一种和过程有关的活动，而过程不仅仅出现在计算机上。P/NP问题归根到底与自然本身的极限有关，与生物和物理系统进化的极限有关，甚至可以说与人类思想所能达到的极限有关。只要P/NP问题还是一个未解之谜，人类就无法确切地知道自己所能取得的成就的极限在哪里。这不由得让人感到精神一振。