冷战时期出现了哪些逆天的黑科技？ 第1页

那些能够在后来变成主流的黑科技，才是真正逆天的黑科技。来讲几个和计算机科学有关的例子吧：

最令人扼腕的黑科技：1973年，一位叫做列奥尼德列文的苏联天然气工程师在一次seminar中，讲到了他所发现的一个具有如下性质的问题集合：这个集合中每一个问题都可以由不确定性图灵机在多项式时间内完成，同时每一个不确定性图灵机在多项式时间内可解的问题都可以在多项式时间内归约到这个问题。定义有点儿绕，但是这个集合却触及到了计算机科学的一个核心问题，后世将这个集合命名为NPC。

当时参与seminar的其他工程师当场就炸了锅，纷纷表示“我裤子都脱了你就给我讲这个”，“你天天研究这破问题，能实现共产主义吗”。年轻的列文没有得到认可感到很郁闷，但是他直觉上觉得自己的这个发现可能对于人类有着重要意义，于是他试探性地去向自己的师尊，伟大的Kolmogorov求助。Kolmogorov表示我正在准备下一次数学家大会时跟那些狗娘养的继续拳击赛，帮不了你太多，这样吧，我给你一份密函，你带着他就可以穿出铁幕到铁幕外去碰碰运气。

于是列文历经艰难险阻逃出了苏联，一路上与KGB的斗智斗勇不表，总之在最困难的时候，他靠着念诵普希金的诗歌汲取力量，终于踏上了自由的国度。到了美国，列文发现他的社会主义phd竟然不被承认，只好勉为其难在MIT再修一个phd。结果办公室椅子还没坐热，就听到同学们纷纷相传对手学校的一位叫做Cook的少侠刚搞出来了一个“Cook归约”，列文当时心生一种不祥预感，翻开论文一看，我靠这不就是我的列文定理吗？后面的事情大家都知道了，Cook拿了图灵奖平步青云被多大请去做了faculty，列文毕业之后心灰意冷去了波士顿大学拿到了一个knuth奖作为安慰。好在那个定理后来被称作库克-列文定理了，这位伟大的铁幕下的斗士最后算是有了一个名分。

成色最足（最“黑”）的黑科技：列文和库克研究上的撞车给我一种很浓的宿命感，为什么这么说，因为这两位的导师也小小地撞过一把。库克的导师叫王浩，在大多数中国人眼里，这个人只是一个传记文学作家。很多人不知道其实王浩在最强人类哥德尔那里耳濡目染之后，还搞出了一个充满东方风情的叫做王浩毯的东西，并证明了这个毯子与图灵机的等价性。看到这里你可能会觉得lambda演算比这不知高到哪里去了，但是这个东西的黑科技属性可不止于此。因为直到现在，美国和欧洲的一帮造人工大脑的疯狂科学家都还在基于这个毯子的研究路线上越走越远。

花开两朵各表一支。20世纪60年代在遥远的莫斯科，kolmogorov面对着西伯利亚升起的朝阳陷入了沉思。此时的kolmogorov刚刚完成了概率论公理化的建设，并在当年苏联数学家大会杯上力压亚历山大洛夫拿到了拳王金腰带。貌似在他面前的挑战只剩下伏尔加河上的冬泳了。然而就在这个时候kolmogorov开始了思考随机序列的本质。可能是命运的安排吧，研究了大半辈子正派武功，说出过“要从公理开始建立数学学科”的kolmogorov，这一次做出了一个乍一听起来有点儿科幻的选择，他说，忘了测度论什么的吧，这一次我要用turing machine。于是一个涵盖或者说统一了了随机性、算法信息论、可计算性理论的被称为kolmogorov复杂度的理论横空出世。

每一次看到kolmogorov复杂度这个名字，我都想把红警3的苏维埃进行曲循环播放一百遍。无论从研究目的、研究方法以及研究成果来说，铁幕时代的其他黑科技都无出其右者。这件事情启发了我无论对于多么逆天的黑科技，扎实的基础都是必不可少的先决条件。就像梅斯云度大师，如果没有对force的完美掌握，就不会有Vapaad的潇洒快意。

最有影响力的黑科技：其实上面的kolmogorov复杂度在机器学习领域也有应用，但是相比下面这个黑科技，其在影响力上就要黯然失色了。想必很多人都猜到我要说什么了，在1971年，也就是前面提到的库克发现NPC存在性的那一年，两位铁幕下的统计学家搞出了一个叫做VC维的概念。这个理论彻底地改变了机器学习作为一个计算机边缘学科的命运。

别看VC理论在现代已经成为了主流，但是黑科技与否，也要结合其出现的年代来看。让我们看看那个时代的其他人都在做些什么，首先，统计学家们当时，以及一直以来，都在搞方差。我曾经听张潼老师在他的讲座中毫不吝啬地赞叹说这个东西让主流的统计学家去搞，再搞几十年都想不出来（注意根据上下文，这里绝不是说统计学家的才能不行，仅是在说VC维的剑走偏锋，所以是统计学家官方认证其为黑科技。。。）。其次，当时的计算机科学家都在做什么呢？1984年PAC被提出，其作者Valiant后来凭借包括PAC在内的一系列贡献得了图灵奖。而PAC在刚提出只能搞搞有限假设集合。另一方面，一些犹太人计算机科学家还在死磕perceptron在“第m+1个样本”上的错误率。

那么为什么说VC理论是最有影响力的黑科技呢，简单列举几组数据：在google scholar上，VC维的创始人Vapnik的总citation是153,797次，SVM算法的提出人之一Cortes的citation是23,967次，实现了svm工具包的cjlin有50,386次。更深一步分析，machine learning作为现在cs最火的方向之一，能够吸引到这么多研究者，是与VC理论将其变得高大上分不开的。

（明知道这个问题已经很久远了，但是还是忍不住回答一下。本回答中除了学术内容以外，还存在着大量的演义内容，请各位以娱乐的心态看待。。。）