数学史 · 中文镜像

数学家传记

莱斯利·瓦利安特Leslie Valiant

出生
1949年3月28日 匈牙利布达佩斯

莱斯利·瓦利安特是一位英美计算机科学家,对理论计算机科学的许多方面做出了基础性贡献。

完整传记

莱斯利·瓦利安特的父母是瓦利安特和Eva 茹利亚 Ujlaki。他在英格兰长大,就读于北希尔兹的泰恩茅斯高中。这所学校在瓦利安特离开数年后,于1969年更名为诺勒姆高中。瓦利安特在伦敦哈默史密斯国王街的拉蒂默中学完成了他的中学教育。这所学校过去(现在仍然)是一所著名的选拔性独立学校,其声誉可追溯到1624年由Edward Latymer创立之时。从拉蒂默中学毕业后,他进入剑桥大学国王学院学习,获得第一个学位——数学学士学位后,他进入伦敦帝国理工学院学习理论计算机科学。在获得帝国理工学院计算机科学文凭后,瓦利安特前往华威大学,在Michael Stewart Paterson的指导下攻读计算机科学博士学位。

在获得博士学位之前,瓦利安特于1973-74年在美国宾夕法尼亚州匹兹堡的卡内基梅隆大学担任访问助理教授。1974年,他凭借学位论文Decision Procedures for Families of Deterministic Pushdown Automata获得华威大学博士学位。瓦利安特与他的学位论文导师M S Paterson合作,于1973年在波恩向Erste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen Ⓣ(计算机科学学会自动机理论与形式语言首届研讨会)提交了论文Deterministic one-counter automata。Wilfried Brauer审阅了该论文,写道:-

确定性单计数器自动机(doca)是一种具有单元素栈字母表的确定性下推自动机。容易看出,doca的包含问题和交集为空问题都是不可判定的。与此相反,作者给出了doca等价性的判定过程,并证明其时间复杂度上界为被测doca状态数的平方根左右的指数函数。他们猜想,对于所有确定性下推自动机类,等价性是可判定的。

瓦利安特于1974年发表了论文The equivalence problem for deterministic finite-turn pushdown automata。S A Greibach指出了这篇论文的重要性:

如果下推存储自动机(pda)在任何输入的任何计算过程中,从压入(增加下推存储长度)切换到弹出(减少下推存储长度)的次数有一个统一的界,则称其为有限转向的。作者确立了确定性有限转向pda的等价问题(两台机器是否接受相同的语言?)的可判定性。该结果的重要性在于确立它所用的证明技术,以及它代表了在解决长期悬而未决的猜想——确定性pda(dpda)的等价问题是可判定的——方面的重大突破之一(已知相应问题对于非确定性pda即使是非常受限的情形也是不可判定的)。

1974年从美国返回后,瓦利安特在利兹大学获得讲师职位,并在1974-76两年间在那里工作。让我们再举一个他早期论文的例子,这篇论文同样是与M S Paterson合作撰写的。这篇1975年的论文Deterministic one-counter automata以以下作者引言开头:

我们提出对确定性单计数器自动机的分析,以表明它们的等价问题是可判定的。我们所有的论证和结果都可以直接翻译成模式理论术语。由此得出的推论是,即使允许Janov模式使用辅助计数器,其等价性也是可判定的。

瓦利安特于1975年搬到苏格兰,在爱丁堡大学担任讲师。1977年,他与Gayle Lynne Dyckoff结婚;他们有两个儿子Gregory John Valiant和Paul A 瓦利安特。在爱丁堡,他于1981年被提升为高级讲师,但在1982年前往美国,当时他是哈佛大学的访问教授。那年晚些时候,他被任命为哈佛大学Gordon McKay计算机科学与应用数学教授。他留在哈佛,尽管1987-88学年他在英国牛津大学做访问研究员。2001年,他被任命为哈佛大学工程与应用科学学院的T Jefferson Coolidge计算机科学与应用数学教授。

瓦利安特做出的贡献非常卓越,他因成就获得了最高荣誉。他于1985-86年成为古根海姆研究员,并于1986年获得罗尔夫·内万林纳奖。他于1991年当选为伦敦皇家学会会士,次年当选为美国人工智能协会会士。他于1997年获得美国计算机协会算法与计算理论特别兴趣小组和电气与电子工程师协会计算数学基础技术委员会颁发的高德纳奖。他于2001年当选为美国国家科学院,获得了欧洲理论计算机科学协会奖,以及美国计算机协会2010年艾伦·图灵奖,该奖将于2011年6月4日在加利福尼亚州圣何塞举行的协会年度颁奖宴会上颁发给瓦利安特。该奖项还包括250,000美元的现金奖励。

我们尚未解释瓦利安特因何获得最高奖项的贡献。为此,我们引用伴随艾伦·图灵奖公告的评论(下文引用的2011年文章引用了该评论)。评论开头写道:-

在过去30年中,瓦利安特对理论计算机科学的许多方面做出了基础性贡献。他的工作开辟了新领域,引入了巧妙的新概念,并呈现了极具原创性、深度和美感的结果。瓦利安特的工作一次又一次地真正定义或改变了计算机科学研究的格局。

接着,它详细介绍了瓦利安特做出惊人贡献的几个领域。我们从四个领域中各摘录一些简短片段:

  1. 计算学习理论。瓦利安特最伟大的单一贡献可能是他的论文《可学习理论》(1984),该论文奠定了计算学习理论的基础。... 瓦利安特的“可能近似正确”(PAC)模型为学习这一概念本身提供了优美的基础。
  2. 枚举的复杂性。在20世纪70年代初,计算复杂性通常处理决策问题的难度,例如一个图是否有完美匹配,或者旅行商是否能找到一条至多一定长度的路线。... 瓦利安特最引人注目的发现之一是,计数问题比以往经验所暗示的要微妙得多。计数问题要求计算某些组合对象的数量:例如,一个图中有多少个完美匹配?我们不仅仅是在问那个数字是否为正的决策问题,还要问它有多大。如果决策问题很难,那么计数问题也一定很难,但瓦利安特令人惊讶地意识到,反之则不成立。在他的论文《计算永久项的复杂性》(1979)中,他表明,尽管存在一种高效算法来判断一个图是否有完美匹配,但不存在高效算法来计算完美匹配的数量(除非P = NP),事实上,计算完美匹配与任何计数问题一样困难。这对计算复杂性社区来说是一个冲击,该社区已经习惯于认为决策问题能轻易捕捉问题的关键特征。
  3. 代数计算。对计算复杂性的另一个关键贡献是瓦利安特的代数计算理论,他在其中建立了一个框架,用以理解哪些代数公式可以被高效求值。……在其论文《代数中的完备性类》(1979)中,瓦利安特用线性代数中两个基本且密切相关的函数,即行列式和积和式,刻画了代数计算的难度。
  4. 并行与分布式计算。除了计算学习理论和计算复杂性之外,瓦利安特做出重要贡献的第三个广阔领域是并行与分布式计算理论。他在这里的成果范围从简单却有力而优雅的洞见,到重新审视最根本的基础。一个简单洞见的例子是他在论文《一种快速并行通信方案》(1982)中描述的并行路由方案。

我们以完整引用艾伦·图灵奖引文的结论来结束这篇传记:-

人们很少见到像瓦利安特的工作那样兼具深度与广度的惊人结合。他确实是理论计算机科学中的一位英雄人物,也是以其勇气和创造力处理科学中一些最深未解问题方面的榜样。

尽管我们已经从艾伦·图灵奖的评注中引用了一些篇幅,读者可能仍希望阅读完整的评注。见Valiant's Turing Award Commentary。

参考文献

正文里的方括号编号指向这里,悬停即可直接看到条目。书目保留原文——译了书名反而查不到文献。

延伸资源

原站列出的延伸阅读与外部数据库,照原样保留,目标多为英文页面。

相关专题

原站的交叉引用。指向本站已镜像专题的留在站内,其余仍指回原站。