4.3　起个好名字有那么重要吗

卡普的论文给出了我们今天使用的P和NP这些名字。但是该怎么称呼那些NP中最难的问题呢？库克用了一个非常学术的名称deg({DNF 重言式})，而卡普使用了术语（多项式时间）完全。可是这些名字太别扭了。

高德纳接手了这个命名问题。鉴于他一贯杰出的研究工作以及宛如丰碑般的三卷巨著《计算机程序设计艺术》¹，高德纳在1974年获得图灵奖。由于认识到了P/NP问题至关重要的作用，高德纳想在第4卷中最终敲定这个NP中最难问题集合的命名。1973年，他通过普通邮件做了一次投票调查。他直到今天都坚持不用电子邮件，这在业界是很有名的。但在1973年，只有普通邮件可用。

^{1 《计算机程序设计艺术》卷1 、卷2、卷3、卷4A的英文版均已由人民邮电出版社出版，中文版也会相继呈现给读者，详情请登录图灵社区（www.ituring.com.cn）查阅相关图书。——编者注}

高德纳在投票中给出的几个候选项——herculean（艰巨）、formidable（可怕）和arduous（费劲），都不怎么受欢迎。他收到了许多来信建议，有些很直白，如intractable（顽固）和obstinate（执拗），有些则更加口语化，如hard-boiled（原意是煮得很硬的蛋，可能是在向库克致敬²）和hard-ass（抗揍的混蛋，简直像可满足性问题一样难啃）。

^{2 库克（Cook）这个姓的原意为“厨师”。——译者注}

最终获胜的来信建议是“NP-complete”（NP完全），它由新泽西州贝尔实验室的几个人提出，是那里的研究者经过多次讨论之后产生的。“complete”（完全或完备）这个词出自数学逻辑学，一个事实集合被称为完备的，就是说它能解释某些逻辑系统的所有真命题。类似地，“NP完全”表示这些NP问题的集合强大到能够用来解决任何其他的NP问题。

高德纳对这个民选结果不太满意，但也没有觉得它差到让人活不下去的地步。他本人特别想要找一个英文词，既能捕捉“困难的搜索问题”这个直观的意象，又要琅琅上口，便于向大众普及。1974年，高德纳总结了他的调查过程，文中写道：“‘NP完全’这个名字其实学术气息有点儿浓，不好向大众推广，但也没有差到不能用的地步。”

“NP完全”很快成为标准术语。高德纳用了大概40年才完成巨著的第4卷。

其实高德纳当年本应该坚持己见，为“NP完全”，甚至“P”和“NP”这些概念敲定一些不那么学术的术语。P/NP问题的重要性已经远远超出了计算机科学领域，而这种将术语的首字母缩写的命名方式，阻碍了门外汉对其重要性的认知。但这些术语在几十年后已经在文化中根深蒂固，即使现在我们想到了更好的名字，恐怕也不好纠正了。

高德纳也意识到，如果最终证明P=NP，也就是说NP完全问题其实就是P中的问题，那么之前为它起名字而做出的种种努力岂不全都白费了。但是高德纳说了：“即使将来可能觉得尴尬，我也愿意冒这个险——我将奖给第一个证明P=NP的人一只活蹦乱跳的火鸡。”所以现在证明P=NP的人可以赢得100万美元，外加一只火鸡。