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

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

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

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

高德纳在投票中给出的几个候选项——herculean(艰巨)、formidable(可怕)和arduous(费劲),都不怎么受欢迎。他收到了许多来信建议,有些很直白,如intractable(顽固)和obstinate(执拗),有些则更加口语化,如hard-boiled(原意是煮得很硬的蛋,可能是在向库克致敬2)和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万美元,外加一只火鸡。

目录