前天买到了刘慈欣《三体II:黑暗森林》,一晚上就看完了。
之所以吓人,是因为“两条基本公理和由此形成的推论”的确显得很有道理。星际文明之间的抑制甚至毁灭,与罗伯特·J·索耶的《计算中的上帝》有类似之处。
其中有很多好玩的细节,比如,引用《2001:太空奥德赛》和《银英传》的只言片语。印象最深的,是三体无人侦查器“水滴”击溃人类舰队的场面,为了描述三体世界明显高于人类的科技水平,举了一个程序员才能看懂的例子:
……无情杀戮在继续,随着四面逃窜的舰群间距的拉大,“水滴”很快把自己的速度增加到60千米/秒。在不间断的攻击中,它显示了冷酷而精确的智慧:追击路线完美地解决了邮差问题。这些精确测量和运算,都是在目标位置不断高速移动的情况下,不动声色地完成……
|
邮差问题是NP-COMPLETE问题,目前还没找到多项式时间内结束的可行算法。当然,四十年来也没人证明它不可解。NP-COMPLETE问题若有突破,图灵奖是拿定了。我们pFind的肽到蛋白归并算法,本质上等同于二部图划分问题,就是一个NP-COMPLETE。