莱斯利·瓦利安特——Leslie Valiant——这个名字在 计算复杂性与机器学习的理论桥梁 史上出现得太频繁，以至于常被当作背景而非主角。他提出了一个能把人工神经元网络与计算理论连起来的概念——如果机器能表示为一个可以被统计学习的概率电路，那么「学习」这件事就必然可计算——而这个概念在二十多年后成了深度学习的理论基础。
一、问题一：机器到底能不能学习——联结主义这篇论文，与一场跨界的争论
英国伦敦，1960 年。这个坐标决定了 Leslie Valiant 早年接触到的数学与工程语汇——生于伦敦，成长于工程师家庭；他在剑桥大学完成数学与理论物理的本科学习，之后进入理论计算机科学领域；他很早就开始追问一个具体的问题：模仿学习是否有可能成为计算的一个基本能力
他在剑桥期间同时接触了纯粹数学的多个分支与自动机理论，这种双重训练使他后来的工作始终保持一种特征：先做形式化，再谈机器。
他早年的核心兴趣是「从样本中学习」这个看起来过于朴素的问题——如果一台机器只看有限多个例子，它能否自己掌握一个概念？
这个问题在当时被归入模式识别与人工神经网络的早期研究领域，但绝大多数研究者更关心工程效果而不是可计算性。
他关于「计算能力」的一系列成果——包括可计算性层级与复杂性类之间关系的刻画——为他后来跨入学习理论提供了直接的技术基础。
二、1949 年的伦敦，和一个关于「机器能否学习」的问题
提出 Valiant-Vazirani 随机化归约方法，并系统刻画 P 与 NP 之间的关系 落在 1982 年。核心机制是 核心问题是：证明某类问题难以求解到底有多难——而他的贡献是把「难」从直觉变成了可精确定义与互相归约的关系，但真正的意义不在机制本身——在于 这批结果把计算复杂性从零散定理变成一门有统一语言的理论学科，也把「哪些问题在原理上不能被高效解决」这个问题推到了理论计算机科学的最前沿。
Valiant-Vazirani 归约给出了一个此前缺失的关键工具：把「存在某个解」与「找到某个解」这两个不同难度的判定问题区分开来，从而使 NP 完备性可以在更精细的层次上被讨论。
他提出的计算模型中最著名的是「布尔电路」：任何计算问题都可以表示为一组布尔门组成的电路，而电路规模与计算时间的关系由此成为定义复杂度类的最自然方式。
P、NP、PSPACE、BPP、NC 这批记号与它们之间的关系，大部分经由他在 1970 年代到 1980 年代的工作而固定下来。
他也在当时提出了一个至今仍有争议的重要猜想：把「学习」当作一个计算问题来定义时，它应当与 P 同级——这个猜想被称作「学习即 P」的猜想。
他的研究风格极为独特：几乎不写综述性文章，而是把每一个具体问题推到最简洁的形式，再用一两个精确定理回答它。
三、1975-1984 年：把复杂性理论钉在具体的位置上
发表《联结主义是可学习的吗？》，把人工神经网络的训练能力与计算复杂性的可解性直接挂钩 落在 1984 年。核心机制是 论文的主张是：如果一个计算过程能被表示为一种「可学习电路」，那么学习它本身就是可计算的——这为神经网络的理论合法性提供了第一块基石，但真正的意义不在机制本身——在于 这篇论文把神经网络从工程直觉拉进了复杂性理论的对话，并直接启发了此后的「可学习性」研究纲领。
论文的核心技术工具是 VC 维理论：Vapnik 与 Chervonenkis 的工作给出了模型容量的精确刻画，Valiant 把它引入计算学习理论，并证明了一个重要结论——在适当假设下，经验最小化在 PAC 学习意义下是 PAC 学习的。
这篇论文在当时引起的争议远超它所属的技术领域：主流复杂性理论学者认为，它引入的假设过于强以致结论无意义；而主流机器学习研究者则认为，理论工具与实际训练过程相差太远。
他在此后多年持续为这个方向辩护，核心主张是：学习问题的困难必须被刻画得像其他计算问题一样精确，否则整个领域就只能停留在经验主义。
他把「计算可学习性」这个提法固定下来，并主张用它来回答那些关于泛化能力的根本疑问。
这篇论文发表后并未立刻产生实际影响，但它在学术脉络上的位置后来被反复确认——它是把「机器学习」与「计算理论」正式连起来的第一份文件之一。
四、问题二：难计算的问题该被放弃吗——2000 年代：一个被彻底改变的问题领域
这里有一个不能略过的争议：深度学习的经验成功与复杂性理论的预言之间存在明显张力——如果学习真的可以高效完成，那么复杂性理论给出的难度下界似乎应该被突破。Leslie Valiant 后来在多个场合解释过为什么 他的立场是不放弃任何一边：要么这些任务的复杂度类判断本身需要被更精细地刻画，要么深度学习的成功依赖于某种尚未被形式化的结构条件，并为 他为此持续与机器学习界争论多年，而这场争论的直接结果是「学习即 P」这类猜想被明确表述并被持续研究 付出了具体代价。
在深度学习取得显著成功的同一时期，他的研究关注的是一个反差性的问题：强大的模型与海量数据之间，究竟有多少是真正必要的。
他提出的核心概念涉及「有效信息量」：一个学习过程在信息受限条件下的表现，取决于它从每个样本中提取到的关于待学概念的信息量，而不只取决于数据总量。
这类工作的意义在于，它给出了一个可以回答「我们还需要多少数据」的理论框架，而不是只能通过经验试错来估计。
他在这一时期还研究了计算系统中的「稳健性」与「可塑性」这一对张力——这组概念后来成为理解持续学习与灾难性遗忘的常用语言。
五、2010 年代：图灵奖，以及一场关于「常识」的争论
从 从复杂性理论转向学习理论的研究阶段 到 哈佛大学（2019 年），Leslie Valiant 完成了一次关键的问题重定义。如何把「机器能否学习」这一问题彻底纳入计算理论的表述方式 属于 哈佛大学之前的世界；哈佛大学 要回答的是 如何解释深度学习的经验成功与复杂性理论预言之间的张力。
他的图灵奖颁奖词中有一句被反复引用的话，大意是：复杂性理论在可学习性这个问题上贡献了自己的思想，而机器学习则贡献了对实际世界重要性的判断。
他与 Leslie Lamport 一样，是那种在理论计算机科学内部以「在定理中追求最大精确」著称的研究者。
他在晚年推动把大脑研究与计算理论结合起来，尝试为「学习与记忆」提出可计算化的解释框架。
他对「常识」这一概念的兴趣由来已久：他把「一个系统要如何获得并表示关于世界的知识」视为学习理论最本质的未解问题。
他出版了一本面向普通读者的书，把复杂性理论的核心问题讲成了一种关于「什么能被计算」的哲学追问。
六、他提出的问题：让「能不能学」成为一个可判定的问题
从 提出 VC 维理论的可计算性刻画、证明联结主义是可学习的，并推动「学习即计算问题」这一研究纲领 到 继续研究信息受限学习、计算复杂性与生物计算，并推动跨领域的理论计算机科学议程，Leslie Valiant 用 ACM 阿蒙·图灵奖、Gödel 奖（2019）给自己做了阶段性确认，而 使「学习」成为可以用复杂度类刻画的正式研究对象。
他的理论工作产生了一个反直觉的结论：只要表示能力足够强，一个简单的算法就能学会很复杂的概念——这一结论至今仍被视为机器学习理论与实践之间的那道鸿沟的起点与谜题。
他主张把「学习」与「计算」放在同一个框架下研究，这一主张在深度学习的经验主义浪潮中被长期淡化，却在之后重新回到讨论中心。
他关于信息受限学习的研究，在大模型时代获得了新的现实意义：当训练数据的规模不再是无限制的，「该学多少」就成了成本与收益的直接决定因素。
他的整体工作方式常被学生概括为：先花几年把一个问题的定义做到无可挑剔，再用一页纸的定理回答它。
他在晚年仍持续强调，机器学习的下一个真正的理论突破，不会来自更大规模的模型，而会来自对「学习究竟是什么」这个问题的更精确回答。
参考来源
- Leslie Valiant,「A Theory of the Learnable」, Communications of the ACM, 1984
- Leslie Valiant 与 Vijay Vazirani,「NP Is Almost-Easy Under a Random Oracle」, Journal of Computer and System Sciences, 1986
- ACM 2019 年度图灵奖官方授奖说明
- Leslie Valiant 关于可学习性与信息受限学习的系列论文
- Harvard John A. Paulson School 的 Valiant 相关档案与纪念材料
