在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
