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

文章预览

来源：返朴 译者按： 本文翻译自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院士描述了柯大师与中学生相处、讲课风格、政治风雨中为学生撑开保护伞，文末，作者给出了对柯大师最后岁月的一个移民者的远观感受。 文中【安德烈·尼古拉耶维奇】即柯尔莫哥洛夫（有时也译作“柯尔莫戈洛夫”） ………………………………