讲座回顾｜沈榆平：From logic to learning: A computational complexity perspective

2026年6月23日，中山大学哲学系逻辑与认知研究所教授沈榆平应邀在研究中心作了题为“From logic to learning: A computational complexity perspective（从逻辑到学习：一种计算复杂性视角）”的学术讲座。讲座从计算理论的基本概念出发，探讨了计算模型、计算复杂度与学习理论之间的联系。华南师范大学哲学与社会发展学院教授熊明担任主持人，学院研究中心师生参加了讲座。

沈榆平教授讲座

沈榆平教授首先介绍了计算领域的若干基础概念，例如计算、问题、编码、复杂性等。以奇偶校验问题（PARITY Problem）为例，沈教授引入布尔电路作为计算模型，介绍了 AC⁰ 与 NC¹ 这两个重要的电路复杂度以及“难问题”的概念。在上世纪80年代初，Yao、Furst、Hastad等人证明PARITY是 AC⁰ 上的难问题，在该领域取得最早的重大突破，证明了 AC⁰ 是 NC¹ 的真子集。尽管Shannon早已在1942年证明 NC¹ 上的难问题存在，但目前为止，学界尚未能给出一个 NC¹ 上难问题的具体构造。因为Razborov和Rudich发现的“自然证明障碍（Natural Proof Barrier）”表明，如果可使用容易验证且足够普遍的自然性质成功证明 NC¹ 的难问题，那么常见的加密技术如RSA就会失效；反过来说，如果我们相信RSA加密系统是安全的，那么就不应该有常见且容易验证的性质来证明 NC¹ 的难问题。

由于 NC¹ 等价于多项式布尔公式可计算的问题，沈教授从一种相当接近命题逻辑的计算模型——命题逻辑程序（Propositional logic program under answer set semantics）入手进行难问题的探索。相较于布尔公式，逻辑程序的主要区别在于前者属于单调逻辑而后者属于非单调逻辑。主讲人沈榆平教授与合作者赵希顺教授的研究证明（Shen & Zhao 2024），奇偶校验问题是逻辑程序中无条件的难问题并给出了具体的指数下界。该结果为理解逻辑程序和布尔电路之间的关系，以及 P 类内的 AC⁰-NC¹ 复杂性分层结构提供了新的视角。

由于逻辑计算和学习概念密切相关，上述结论为计算学习理论的前沿研究提供了一种新思路。沈教授以布尔函数为例阐释了 PAC 可学习性概念，如命题逻辑中的析取范式、合取范式均属于可学习的表示类。他提到，目前严格意义上能够被证明为机器可学习的问题十分有限。尽管布尔函数对人类来说并不难以理解，但 Kearns（M. Kearns & et. 1987）等人证明，若 RSA 加密系统安全，则 NC¹ 类不可学习。这是因为 NC¹ 通常被认为包含了伪随机函数，同样受到自然证明障碍的限制。不过，由于逻辑程序并不会受到自然证明障碍的影响，沈教授由此提出一个开放问题：逻辑程序是否是机器可学习的？如果答案是肯定的，那么基于已知结论，意味着机器能够学习某些 P-完全问题，这将是相关领域的一个重要突破。

与会师生

讲座最后，沈榆平教授回答在场师生的问题，尤其是围绕大语言模型和机器学习理论与实践与听众进行了深入的讨论和交流。本次讲座为华南师范大学逻辑与分析哲学中心的师生带来了逻辑计算领域的前沿研究成果，对中心未来开展相关领域交叉研究起到了积极的促进作用。

文字｜刘烨童

图片｜刘欣

初审｜胡扬

复审｜伍素

终审｜熊明