5.2　东方

当年苏联的“理论控制论”学界活跃着很多重要的人物，而我们的故事将集中介绍其中的三位，他们分别代表处理蛮力搜索的三种方式。

• 谢尔盖·雅布隆斯基，他首次将蛮力搜索的研究聚焦于寻找实现特定计算函数的最小电路，但他的权力欲和傲慢阻碍了俄罗斯的计算复杂度科学的发展。
• 安德烈·柯尔莫哥洛夫，他是伟大的俄罗斯数学家，主张通过代数信息来衡量复杂度。
• 柯尔莫哥洛夫的学生列昂尼德·莱文，他独自研究发现了P/NP问题和NP完全问题，但是由于政治原因，他甚至无法在祖国得到博士学位。

1.谢尔盖·雅布隆斯基

俄罗斯的计算学研究被称为理论控制论，该学科直到20世纪50年代电子计算机在军事上开始发挥重要作用时才正式起步。谢尔盖·弗谢沃洛多维奇·雅布隆斯基生于1924年的莫斯科，二战时曾在苏联军队服役，战后到莫斯科国立大学学习数学。他于1953年获得博士学位，导师是俄罗斯可计算性领域的先驱彼得·诺维科夫。雅布隆斯基和诺维科夫的另一个学生阿列克谢·李雅普诺夫组成研究小组，在莫斯科国立大学举办了一系列关于逻辑函数的研讨会。他们的小组成了俄罗斯计算理论的研究中心。

第4章提到的可满足性问题的处理对象是由基本逻辑运算符AND、OR和NOT组合成的逻辑表达式。我们甚至可以用一串AND、OR和NOT来表达计算过程。有些问题只需要少量的逻辑运算符组成的“电路”，而其他问题需要大规模的电路才能运算。谢尔盖·雅布隆斯基在20世纪50年代研究了这个概念，我们今天称之为电路复杂性。

信息论创始人，美国人克劳德·香农证明某些逻辑函数对应复杂度非常高的电路。雅布隆斯基则研究了生成这些函数的实际难度。听起来是个很困难的任务，但实际上P≠NP的一个强化版本就意味着对于某些描述起来很简单的搜索问题，不存在小规模的电路可以计算它们。

雅布隆斯基首先指出，根据香农的结论，随机生成的函数对应的电路的复杂度接近最大值。接下来他研究了如何不用随机过程就能找到这样的函数。

需要蛮力搜索全部函数吗？他证明任何能生成具有接近最大复杂度函数的过程，必须内嵌所有函数。那么从某种意义上讲，任何能生成高难度函数的过程都能经过修改，以生成任意其他的函数。雅布隆斯基提出，这意味着蛮力搜索是必要的，因为在生成高难度函数的过程中，必须生成每一个可能的函数。1959年雅布隆斯基将他的论文命名为“论在解决电路理论的某些问题时不可能排除蛮力搜索”（On the Impossibility of Eliminating Perebor in Solving Some Problems of Circuit Theory）。

雅布隆斯基虽然证明了一个重要的结论，但他的解释容易误导人。不能根据“从一个高难度函数能生成任意函数”，就推出“生成高难度函数必须生成所有函数”。雅布隆斯基的结论对于寻找高难度函数的计算复杂度没有什么实际作用。雅布隆斯基的学生佐拉夫勒夫在1960年发表的一篇论文标题同样令人印象深刻：“论不可能通过某种类型的算法构造布尔函数的最小析取范式”（On the Impossibility of Constructing Minimal Disjunctive Normal Forms for Boolean Functions by Algorithms of a Certain Class）。这篇论文同样没有谈到代数运算复杂度的问题。这些研究工作实际上和P/NP问题的研究没有什么关系。

当年的苏联不仅在经济上集权，在学术活动上也是如此。雅布隆斯基断定他自己的研究圆满解决了蛮力搜索问题，所以他强力压制在这个方向上的进一步研究，特别是对计算复杂度和算法的研究。雅布隆斯基后来进入了苏联协调和控制数学研究的数学委员会，成为其中颇有影响力的成员，也在20世纪60年代造成了不少的争端，后面将会讲到。

1. 安德烈·柯尔莫哥洛夫

安德烈·柯尔莫哥洛夫于1903年出生在俄罗斯坦波夫市。1920年他考入莫斯科国立大学，最开始学的不是数学，而是历史学。他研究的问题是：俄罗斯在中世纪的征税工作是以户为单位还是以村为单位来开展的。他分析了税收数据，证明如果以村为单位来收税，那么对数据的描述会更简单一些。他把这些结果呈交到历史系，得到了极大的赞扬。于是他询问是否能发表论文，得到的回答却是：“你只有一个证据。在历史期刊上发表文章至少需要两个证据来支持你的假说。”于是柯尔莫哥洛夫放弃历史，转而研究那些一个证据就足够的领域。柯尔莫哥洛夫选择了数学，并通过努力，成为20世纪苏联乃至全世界最伟大的数学家，他对几乎所有的数学领域都作出了基础性的贡献。

图5-3　DILBERT © 2001 Scott Adams。使用本图片需要得到UNIVERSALUCLICK的许可。版权所有，侵权必究

柯尔莫哥洛夫对理解概率和随机性的热忱，直接促成了一个简单却伟大得不可思议的想法。比如下面几串数字：

• 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999
• 707106781186547524400844362104849039284835937688474
• 982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097

中有一串是通过随机数生成器生成的，其他两串通过其他方法生成。上面每个数字序列发生的可能性都是相同的，为什么要认为一个序列比其他序列更加“随机”呢？在继续往下读之前，请大家先猜猜哪串数字真的是随机生成的。

很难认为一个全是“9”的序列是随机生成的。第二个序列可能有人知道它是0.5的平方根小数点后数字的前50位。所以第三个数才是随机选择的。

柯尔莫哥洛夫认识到，一个序列的随机性大小可以通过“最少需要多少字数来描述它”来衡量。第一个序列的描述是“50个9”。第二个序列是“1/√2”。而对于第三个数，最短的描述只能是982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097。“描述”是一个不正规的概念，柯尔莫哥洛夫通过计算机程序的表述把它正规化了。

类似的想法在稍早也先后被两个美国人提出过，他们分别是雷·索洛莫诺夫（出生于克利夫兰州，厌恶自己的俄罗斯姓氏）和格里高利·蔡廷。柯尔莫哥洛夫及其弟子则深化了这个概念，所以这个衡量标准被称为“柯尔莫哥洛夫复杂度”。

随机序列就是指最短描述是本身的序列，比如

982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097

通过随机选择每一位数很容易就能生成随机序列。没有随机数就没有这些随机序列。不存在非随机化的算法能生成任意长度的随机序列。我甚至不知道

982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097

是否真的是一个随机序列，因为必须要测试所有比它短的描述方式，而有些表述方式可能非常复杂。

柯尔莫哥洛夫复杂度的理论背景深厚，并且在机器学习、算法分析和计算复杂度等多个领域有广泛应用。虽然它本身没有直接涉及P/NP问题，但是通过对它的研究，柯尔莫哥洛夫的学生列昂尼德·莱文直接导出了P/NP问题。

1. 列昂尼德·莱文

1961年，李雅普诺夫从莫斯科国立大学转到新西伯利亚国立大学任教，在那里他建立了理论控制学系。新西伯利亚市距离莫斯科有2800公里之遥，是俄罗斯第三大城市，也是西伯利亚最大的城市。

系里的老师大部分是雅布隆斯基和李雅普诺夫以前的学生，来自莫斯科。新组建的理论控制学系很快成为俄罗斯理论控制学的第二大研究中心。鲍里斯·特拉腾布罗在40岁就已经是这个领域的资深研究者，他在中心建成之时就已加入，并很快成为领军人物。1962年，Y. M. 巴兹丁从里加市拉脱维亚大学获得博士学位，并加入了新西伯利亚的研究中心。特拉腾布罗开始和巴兹丁合作，研究计算复杂度的基础理论，许多拉脱维亚和新西伯利亚的学生慕名而来。在20世纪60年代，他们开始建立一个复杂度的算法理论，类似于同时期西方的研究。

但苏联的计算复杂度理论的发展并不顺利，正如特拉腾布罗1984年写的那样：

我们与“主流”的控制论研究者们（主要是雅布隆斯基）之间的关系恶化了，对此感到担心。他们对于将算法理论引入复杂度研究领域的态度十分消极……他们不相信计算复杂度和算法复杂度在蛮力搜索领域起到的作用。这些学术上的分歧很可能因为蛮力搜索上的争议而加深，特别是当雅布隆斯基在那样一个协调和控制数学研究的组织中担任高位之后。¹

^{1 * B. A. Trakhtenbort, “A Survey of Russian Approaches to Perebor Algorithms,” Annals of the History of Computing 6, no. 4 (October 1984).}

柯尔莫哥洛夫于1963年夏天访问了新西伯利亚，他和特拉腾布罗分享了学术成果，探讨了算法理论如何促进对信息和复杂度的理解。

在那次访问之后，柯尔莫哥洛夫很快到了基辅大学，并访问了一个为数学和物理学神童专设的高中寄宿学校。他随便问了几个问题，很多问题都被一个叫列昂尼德·莱文的15岁孩子解答了。柯尔莫哥洛夫后来邀请莱文到莫斯科大学跟他学习。莱文在研究生期间的杰出工作分为两个方向。

首先，莱文发明了一个通用的搜索算法。假设Alice对Bob说她有能快速求解团问题的算法，但是不告诉Bob是什么算法。莱文的技巧能让Bob创造出一个几乎和Alice的算法一样快的算法，而他不需要知道Alice的算法具体是什么。莱文通过柯尔莫哥洛夫复杂度的一个变种发展了自己的理论，基本上是尝试了所有合理的方式，才取得了这个成果。

对搜索的研究使莱文转而思考那些能反映搜索本质的问题，于是他引入了“通用搜索问题”的概念，这个概念基本相当于库克提出的NP完全性。莱文列出了6个通用搜索问题，其中就包括可满足性问题，从而正式建立了P/NP问题。

在莱文取得的这两项令人惊叹的成就中，仅第二项几乎就可以跟为库克赢得图灵奖的那篇论文媲美。然而柯尔莫哥洛夫却认为两个结果无法分开发表，于是他强迫莱文把它们写在一篇论文里。当时俄罗斯的数学出版物的风格导致精简的论文更受欢迎，文中基本不会给出支持结论的证据的细节。莱文把这种风格发挥到了极致，将两项成果写在了一篇只有两页的论文里。

莱文在苏联申请博士学位的时候，没有把这篇杰作包括在论文集里。当时所有苏联年轻人都是苏联共产主义青年团团员。莱文经常在共青团的活动中调皮捣蛋，他低估了这些行为的后果。这些行为最终导致他没有被授予博士学位，因为政治不合格。

莱文在苏联无法摆脱政治问题的纠缠，他想方设法在1978年移民到了美国。艾伯特·梅耶将他录取为麻省理工学院的研究生，由于他以前的研究工作太厉害，第二年就拿到了博士学位。后来莱文到波士顿大学担任教授，直到今天。

莱文的工作在20世纪70年代中期才被美国所知晓，那时P/NP问题已经广受关注。莱文没能分享库克1982年的图灵奖，而直到20世纪80年代末期，人们才把NP完全性的早期结果称为库克–莱文定理。

20世纪80年代后，苏联与美国的关系开始缓和。一名俄罗斯学生亚历山大·拉兹波洛夫为一种通过电路复杂度理论来证明P≠NP的方法做出了重要贡献，这个故事我们留到第7章再讲。

随着苏联的解体和互联网的崛起，俄罗斯数学研究者的工作不再与世隔绝。计算复杂度领域真正成为全球性的研究课题。