当我们反思P和NP问题时，我们看到这个问题有很多不同的含义。P和NP的数学正式定义仍然是它的官方定义，虽然很冷冰冰但是含义最为完全。而且能够解决这个数学问题的人还能给你的到数百万美元的赏金不是吗。有时候，我们虽然可以通过可计算理论、电路、证明和代数几何等工具看到解决P和NP的方法，但是目前没有能够完全解决P和NP问题的有力方法。从这个角度上来说，我们正在抽象P和NP问题到一些领域中，降低了它的难度，也就是距离原问题越来越远。在现实生活中，我们也有很多秉待解决的实际NP问题。在1976年出版的经典著作《计算机与难处理性：NP完全性理论指南》一书中，Garey和Johnson举了一个倒霉的员工的例子，他老板让他去解决一个NP完全优化的问题。最终的时候，这个员工苦恼地找到老板说，我实在没辙了，找不到一个有效的算法来解决这个问题，而且不光是我，这个世界上不管是比尔盖茨还是沃兹尼亚克都束手无策。书中说，这个老板不应该解雇这名员工，因为没有其他的人能够解决这个问题。在P和NP的早期，我们将NP完全性视作障碍。这些是我们无法解决的问题。但是随着计算机的发展和进步，我们发现可以通过启发式与暴力计算的组合，在很多NP问题上取得很好的进展。在Garey和Johnson的故事中，如果我是老板，我可能不会解雇那名倒霉的员工，而是建议他使用一些新的方法，比如混合整数编码、机器学习以及暴力搜索的方法进行破解。NP完全意味着不可能，这个想法其实已经out了，它的时代也已经成为过去式了。NP完全，只是意味着可能没有始终有效和可扩展的算法而已，但是问题，还是有可能被解决的。在我2013年发表的P和NP的书中，我有一章名为“美丽新世界”的文字。我在其中提到了一个理想化的世界，在那里，捷克数学家证明了P=NP，从而为所有NP问题提供了一种非常有效的解决算法。虽然我们不会也可能永远不会生活在这样的理想世界中，但是随着医学的进步，随着虚拟世界、元宇宙等新概念的崛起，P=NP这个古老的美妙话题似乎也不再遥不可及。但是，话说回来，我们正在朝着几乎能够颠覆P=NP问题思想的方向大步前进。与其一直将其视为算法的障碍，不如去想象P和NP的解决之道，在其中探索一些新的方向，发掘出其中不可能的可能性。原文链接：https://cacm.acm.org/magazines/2022/1/257448-fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/fulltext【 旅行商|P vs. NP 五十年：AI正在解决不可解问题】
