5.3　哥德尔的信

1956年，库尔特·哥德尔写信给约翰·冯·诺依曼，后者是计算机科学和其他许多领域的先驱。在这封（用德语写的）信里，哥德尔讨论了可满足性问题，并用一种不同的术语规范化了P/NP问题。他提出如果我们生活在P=NP的世界里，那么“数学家思考‘是或否’的思想工作将完全由机器来代替……而我个人认为，这完全是有可能发生的”。这封信的写作时间比库克和莱文的论文发表早15年。

我们不知道冯·诺依曼是否回复了这封信，甚至不知道他是否看到了它。冯·诺依曼那时已经身患癌症，不久就于1957年辞世。这封信则直到20世纪80年代才为科学界所知。哥德尔在1978年去世，然而他晚年已经神志不清，无法注意到库克只是重述了他提出的问题。

既然是哥德尔早于库克和莱文发现了P/NP问题，为什么我们不把P=NP称为“哥德尔问题”，以肯定他的贡献呢？因为科学领域遵循的是哥伦布原理：哥伦布出名并不是因为他第一个发现了美洲，而是因为他最后一个发现了美洲。哥德尔本人也不是没有问题。他自己都没有意识到当年向冯·诺依曼提出的这个问题的重要性，不然他不会在之后的任何一个公开场合都没有提出这个问题。库克和莱文仍然是率先发表论文，并向学术界呈现P/NP问题的人。

为纪念哥德尔为逻辑学作出的奠基性贡献以及哥德尔的这封重要信件，理论计算机科学界于1993年设立了哥德尔奖，表彰该领域近期发表的杰出研究论文。