计算复杂性理论先驱Levin：一个中学生眼里的柯尔莫哥洛夫老师

Leonid Levin2024年06月12日约 6 分钟

译者按：

本文翻译自Leonid Levin（1948-）为他的老师柯尔莫哥洛夫（Andrey Nikolaevich Kolmogorov，1903-1987）写的纪念文章Колмогоров глазами школьника и студента ，原为俄文。感谢Levin院士允许我翻译他的文章。

Leonid Levin院士研究领域是随机、算法复杂性、信息论、计算理论等。他是NP完全问题的发现者，给出了NP完全定理（Cook-Levin定理）。他被写入Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists，这本书中也提到了本译文开头写的他与柯尔莫哥洛夫在其创建的数理特长中学的初见。

Lenoid levin

Levin院士描述了柯大师与中学生相处、讲课风格、政治风雨中为学生撑开保护伞，文末，作者给出了对柯大师最后岁月的一个移民者的远观感受。

文中【安德烈·尼古拉耶维奇】即柯尔莫哥洛夫（有时也译作“柯尔莫戈洛夫”）。

撰文 | Leonid Levin

翻译 | 宋维凯HEOM

我第一次见到柯尔莫哥洛夫老师是在15岁那年，当时他参观了基辅物理和数学寄宿学校（译者注：一所数理特长中学），我在1963-1964年在那里就读。我已经从科普杂志上知道了他的名字，但他给我的第一印象是出乎意料的：他没有和在他访问之际涌入寄宿学校的“大人物”待在一起，而是决定与学生见面。与任何其他院士都会照本宣读的无聊讲座不同，柯尔莫哥洛夫开始用有趣的问题来考我们。他将问题抛给大家，给我们几分钟的时间思考，并听取了回答。我解决了其中的一些问题，他记住了我（我在很久以后才知道，他顺便笑着提醒我注意一些可能不太讨人喜欢的细节）。也许这在他决定允许我转到他负责的莫斯科物理和数学寄宿学校（译者注：即现在的柯尔莫哥洛夫中学）时发挥了作用。（所有其他审定人员都拒绝了，虽然我有一个理由：我父亲当时在莫斯科，是一名研究生。但我真的很想去，从不放弃的父亲得到了一次交谈机会：在一次演讲中奇迹般地“抓住”了柯尔莫哥洛夫。）

在寄宿学校，柯尔莫哥洛夫亲自给我们讲授课程。他还带我们去远足，给我们朗诵诗歌【我记得维克多·索斯诺拉（Victor Sosnora，1939-2019）】，安排古典音乐会，从家里带来唱片。他不断地鼓励我们不仅要对数学和物理感兴趣，而且要全面发展。我们喜欢远足和诗歌，但对音乐所知甚少——这毕竟需要相关专业知识。学校倡导对“社会科学”感兴趣让我们又笑又恼，柯尔莫哥洛夫本人对此保持沉默是件好事。

他选择了在学校中很不寻常的讲座主题：伽罗瓦理论、直觉逻辑等。后来我反复听到让我吃惊的意见：他们认为柯尔莫哥洛夫是一个糟糕的讲师。然而，在十五六岁的我的眼里，他是最好的讲师。很多人认为，孩子们对这么陌生的想法无法接受，这是一种误解。孩子在生命的第一年比成年人几十年里学到的新事物都多。孩子们比大人做的唯一差的事情就是忍受无聊。但是柯尔莫哥洛夫老师的讲座一点也不无聊！当然，内容很难，然而我们充满激情，全力以赴。此外，讲座结束后，我们努力去完成由柯尔莫哥洛夫的助教阿列克谢耶夫（Vladimir Mikhailovich Alekseev，1932-1980）、索辛斯基（Alexei Bronislavowitsch Sossinsky，1937-）精心挑选的题目。

柯尔莫哥洛夫的讲座中包括了新近的发现，他鼓励我们去思考未知的事物。那段时期，我证明了一些新定理，得到了安德烈·尼古拉耶维奇的赞许。他在莫斯科数学会提到了它们，并建议我向《苏联科学院报》写一篇短文。（但我安排事情节奏混乱，直到几年后才写成。）

在大学学习期间，我有机会将柯尔莫哥洛夫的讲座与马尔科夫（Andrey Andreyevich Markov，1903-1979）关于类似主题的讲座进行比较：对比是惊人的。（译者注：这是提出“马尔科夫链”那位数学家的儿子，是构造数学和逻辑方面的专家。）马尔科夫始终如一地讲解，一步接着一步。柯尔莫哥洛夫则是一下子把世界上的一切都讲出来，他能将意想不到的东西连接起来，但每一个都与若干其他节点连接，众多连边若隐若现。他构建了一个指数级快速分支的“网络”，从整体上很难看清脉络关联，但每个部分都很有趣。我开玩笑说，马尔科夫和柯尔莫哥洛夫的演讲风格遵循他们各自给出的算法定义。（马尔科夫的算法基于线性字符串的逐字母的渐进变换；Kolmogorov–Uspensky的算法基于自由分支图。）

柯尔莫哥洛夫当时喜欢的话题——复杂性、偶然性、信息的一般概念——让我非常兴奋。像许多年轻人一样，我一直在试图追求最基本的概念。但是诸如逻辑或算法理论之类的“基本”理论，它们的“定性”性质使我感到困惑——没有什么可以“计算”的。柯尔莫哥洛夫为这些领域带来了丰富的定量工具。事实上，回到基辅，我试图给复杂性下一个定义【我称之为“非自然”（неестественность）】，但我无法证明它的不变性。在莫斯科，我把我的失败告诉了索辛斯基，他问柯尔莫哥洛夫，给了我一个惊人的回答：柯尔莫哥洛夫刚刚证明了我做不到的事情，他的详细文章即将发表！然后我决定不惜一切代价进入莫斯科国立大学，成为安德烈·尼古拉耶维奇的学生。

我恐怕柯尔莫哥洛夫老师不止一次后悔做我的导师。我是一个吵闹、不规矩的学生，对所有问题都有自己的看法，让责任感强的人不得安宁。对于任何需要替罪羊的人来说，我也是天赐之喜。这种需求是在 1960 年代后期莫斯科国立大学“意识形态工作崩溃”之后出现的。安德烈·尼古拉耶维奇坚定地为我辩护【在莫大杰出的校长彼得罗夫斯基（Ivan Petrovsky，1901-1973）的帮助下】。与领导当局意见相反，我最终得以留在莫斯科国立大学，甚至与柯尔莫哥洛夫一起开了一个讨论班。我记得，老师在讨论班上抱怨他自己“落后”和“老”了，但他不仅比我们所有人都更快地掌握我们尚未注意和理解的新想法，而且活跃地表达意想不到的深刻见解。

但时代变了。彼得罗夫斯基校长去世了（听说是在与“高层”进行了艰难的谈话后心碎而死）。心怀不轨的莫大党委书记亚戈金成为莫斯科市委秘书和副手、中央委员会科学部的领导。按照新的标准，谨慎的柯尔莫哥洛夫几乎变成了持不同政见者。我成为所有与我有联系的人的负担；我无法在正式的科学机构工作，甚至无法参加研讨会（参与者被要求上报我的到访情况）。我在莫斯科的存在开始变得毫无意义。柯尔莫哥洛夫老师甚至告诉我，当局要求他和我谈谈这件事。几年来我一直抗拒移民的想法，但最终，在1978年，我下定了决心。

令我感动的是，柯尔莫哥洛夫老师不顾他一贯的谨慎，邀我当面告别，并送给我一本非常美丽的古代俄罗斯建筑相册，甚至题字（尽管他只用了名字中的首字母签名）。

当然，我不能从美国给他写信——那会使他面临不必要的风险。远远地，我绝望地看着这位伟大科学家如何被排斥，他的健康如何被破坏，以及他在“改革”伊始逝去，而没有机会看到新的时代。

本文经授权转自宋维凯HEOM， https://zhuanlan.zhihu.com/p/446319224，有修订。原文收录于《柯尔莫哥洛夫学生回忆集》（Колмогоров в воспоминаниях учеников，МЦНМО, 2006）

来自同一个声音

一次发错的诺奖，却给对了人

奠定现代物理的五大成果为何没拿诺奖；同行评审也开始“外包” | 科技周览

叶军与Bloch共获2026年沃尔夫物理学奖

今年诺奖你押谁？2026年诺贝尔生理学或医学奖预测