格雷沙姆讲座系列之《多难才算过难？—— 复杂性理论入门》by 科尔瓦・玛丽・罗尼-杜加尔（Colva Mary Roney-Dougal）教授

★置顶zzllrr小乐公众号，追踪《小乐数学科普》系列报道！

部分数学问题可借助计算机轻松求解，还有一些问题或许根本无解。复杂性理论便是用来界定问题难度的理论体系，而数学界最知名的未解难题之一，便是P是否等于NP这一命题：倘若一道问题的答案易于核验，那么这道问题本身是否也容易求解？

本次格雷沙姆讲座先介绍艾伦・图灵（Alan Turing）及该领域其他先驱学者的相关研究，再为大家梳理该领域近期取得的各类研究进展。演讲者是一位专攻群论与计算代数领域的英国数学家，科尔瓦・玛丽・罗尼-杜加尔（Colva Mary Roney-Dougal），她是圣安德鲁斯大学纯数学教授，大英帝国官佐勋章获得者，爱丁堡皇家学会会士。

作者：科尔瓦・玛丽・罗尼-杜加尔（Colva Mary Roney-Dougal，圣安德鲁斯大学纯数学教授）2026-5-11

译者：zzllrr小乐（数学科普公众号）2026-5-17

求喜欢

演讲人简介

科尔瓦・玛丽・罗尼-杜加尔（Colva Mary Roney-Dougal）大英帝国官佐勋章获得者，是一位专攻群论与计算代数领域的英国数学家。她现任圣安德鲁斯大学纯数学教授，也是该校首位纯数学系女性系主任。

罗尼-杜加尔教授本科就读于圣安德鲁斯大学，起初她入学时主修英语与哲学专业，之后才决定投身数学研究。她于伦敦玛丽女王大学取得博士学位，随后先后在悉尼大学、圣安德鲁斯大学计算机科学系从事博士后研究，并于2003年入职圣安德鲁斯大学数学系担任永久教职，此后便一直在该校任职。

她的研究领域涵盖群论（研究对称性的数学分支）、组合数学（计数相关的数学分支）以及计算数学；她在2013年与约翰・布雷（John Bray）博士、德里克・霍尔特（Derek Holt）教授合著的研究专著《低维典型群的极大子群》The maximal subgroups of the low-dimensional classical groups，迅速成为该领域的经典参考文献。

除科研工作之外，罗尼-杜加尔教授十分热衷于向大众科普数学知识。2024年，她因在数学与教育领域作出的贡献被授予大英帝国官佐勋章。

主持人（萨拉・哈特）：

各位晚上好。大家好，我是萨拉・哈特，十分荣幸由我开启今晚活动的开场环节，我曾担任格雷沙姆学院几何格雷沙姆讲席教授。我热爱数学，相信在座各位也同样热爱。今晚大家将会收获一场精彩的讲座。初次来到本校的各位朋友，本次讲座是格雷沙姆学院与伦敦数学会每年联合举办的学术讲座，稍后我们将有请伦敦数学会的代表上台发言。

接下来由我以格雷沙姆学院代表的身份，提醒大家相关安全事宜：会场后方设有应急安全出口，位置就在灯光所在处。我们暂未收到火警预警，若意外响起警报，请大家有序撤离，现场工作人员会引导大家前往安全区域。另外，讲座结束后我们预留了五至十分钟的问答交流时间。

线上观看直播的各位观众朋友们，大家晚上好，欢迎收看本场讲座。大家可以扫描二维码进入斯莱多（sli.do）互动平台在线提问。现场在座的各位观众，若想匿名提问也可扫码操作，当然举手提问同样欢迎，我们会依次传递麦克风，请大家拿到话筒后再进行发言，方便全场人员听清问题。我的开场致辞到此结束，接下来有请伦敦数学会的玛丽・马林登为大家介绍今晚的主讲嘉宾，有请玛丽。

嘉宾介绍人（玛丽・马林登）：

谢谢萨拉。各位晚上好，我谨代表伦敦数学会与格雷沙姆学院，欢迎大家前来参与2026年度伦敦数学会 — 格雷沙姆学院联合讲座，本场讲座主讲人为科尔瓦・罗尼 - 杜加尔教授。我是玛丽・马林登，现任伦敦数学会教育委员会主席，本次学术活动由我们与格雷沙姆学院联合筹办，我们对此倍感欣喜。

正式讲座开始前，我简单介绍一下伦敦数学会（LMS）及其行业服务工作。

伦敦数学会始建于1865年，是英国权威数学学术团体。学会核心宗旨是推动数学领域发展、传播数学知识、推广数学应用，目前全球会员规模约三千名。学会始终依托会员群体与广大科研学界，助力数学行业稳步前行。

学会开展的工作内容十分丰富：其一，发放科研与教育专项资助资金；其二，举办各类学术会议与研讨交流会，为取得杰出数学研究成果的学者颁发奖项与荣誉勋章；其三，出版业内认可度极高的数学专业期刊与学术著作；其四，面向大众开展科普讲座，探讨数学教育与数学科研领域的各类行业议题。若大家想要深入了解学会详情与日常工作，讲座结束后可以前来与我交流沟通。

接下来为大家预告两场学会近期举办的学术活动。继本场讲座之后，我们将举办2026年度伦敦数学会与SIAM应用数学及工业数学联合会联合举办的戴维・克雷顿奖项颁奖暨主题讲座，活动将于5月13日在伦敦英国皇家学会举办。该奖项旨在表彰为数学行业发展与学界建设作出突出贡献的知名数学家。

牛津大学艾伦・戈里利（Alan Gorilli）会士凭借其在力学、生物学科研领域及材料研究领域产出的深刻且极具影响力的数学研究成果，同时长期扶持青年数学研究者、积极向大众普及数学及数学应用知识，荣获2025年度该奖项，他也将在本次活动现场领取荣誉奖项。顺带一提，艾伦教授同时兼任格雷沙姆学院几何讲席教授。

下月我们还将开设数学科普传播研讨会，由两位资深数学研究者与科普工作者本・斯帕克斯、凯蒂・斯特克尔斯主讲。研讨会将系统传授面向大众开展数学科普的实用思路与实操技巧，活动面向所有爱好者开放，尤其适合有志于投身数学大众科普事业的人群。该研讨会报名名额十分紧俏，有意参与的朋友建议尽早完成报名。

话不多说，接下来我隆重有请2026年度伦敦数学会 — 格雷沙姆学院联合讲座主讲人登场。

科尔瓦・罗尼-杜加尔教授任职于圣安德鲁斯大学，担任纯数学教授一职，同时兼任该校纯数学系系主任。她本科就读于圣安德鲁斯大学，最初攻读英语与道德哲学专业，后续转入数学专业深耕。之后于伦敦玛丽女王大学取得数学博士学位，博士毕业后前往澳大利亚悉尼大学开展博士后研究工作。

学成归国重返圣安德鲁斯大学后，她先担任人工智能方向博士后研究助理，随后正式入职该校数学系，获得终身教职。其代表性学术著作是收录于伦敦数学会讲义丛书的《低维典型群的极大子群》，该著作一经出版便成为领域内通用权威参考文献，目前引用量已超七百五十余次。2024年，她因在数学教育领域作出的卓越贡献，获英王授予大英帝国官佐勋章，今年又正式当选为爱丁堡皇家学会会士。接下来让我们以热烈的掌声，欢迎大英帝国官佐勋章获得者科尔瓦・罗尼-杜加尔教授，为大家带来本场精彩讲座。

演讲人：科尔瓦・玛丽・罗尼-杜加尔（Colva Mary Roney-Dougal）

非常感谢玛丽细致的介绍，也感谢各位观众在微凉的五月夜晚前来赴约，同时感谢萨拉完成开场主持。或许大家并不知晓，我和萨拉早在攻读博士学位时期便已相识。接下来进入今天的正式讲座内容，我先从一个贴近生活、颇具难度的实际问题说起。

大家不妨设想筹备一场大型家庭聚餐，邀约一百位亲友共同赴宴，安排所有人围坐在同一张餐桌就餐。这个想法听起来十分温馨，但这个大家庭里存在关系不和的亲友，我们不愿让观念相悖、相处不合的人相邻而坐。

为了方便讲解，我暂且缩减人数，选取九位家庭成员作为示例，分别用字母代称，其中包含爱丽丝姨妈、比尔，还有画面下方的祖母与伊恩叔叔几位核心人物。爱丽丝姨妈仅能与比尔、戴维相邻就座，和其他人同坐都会产生矛盾；比尔性格随和，可相邻入座的人数有四位；我本人同样性格开朗，也有四位可共处就餐的亲友，其余人员也都有着对应的相处限制。

大家第一眼看到这份人员相处清单，都会觉得排布就餐座位十分棘手，很难快速规划出一套不会引发矛盾的落座方案。想要解决这个难题，我们首先需要简化问题形式。此前我分享过该案例后，有人向我推荐过一款可统筹六千人大宴座次排布的专业软件，这类软件有着极高的市场需求，只因聚餐人数越多，座次规划的难度就会呈指数级上升。我们可以将座次排布问题转化为图论模型，用简易图示梳理关系。

在图示当中，每一个圆点代表一位家庭成员，圆点之间相连的线条我们称之为边，只要两人之间存在连线，就代表二人可以相邻就餐。在专业定义里，这些圆点称作顶点，连接线称作边。梳理完图示关系后，座次规划就等同于在这张关系图中完成闭环遍历，遍历方向不受限制。

我们需要从爱丽丝姨妈的位置出发，沿着连线走完所有顶点，每位家庭成员仅经过一次，最终再次回到起点，对应着所有人围桌就餐、全员落座无重复的理想状态。

结合图示不难发现这套家庭落座方案存在明显矛盾：爱丽丝姨妈左右两侧只能安排比尔与戴维，祖母又只能坐在比尔与海蒂中间，伊恩叔叔则仅能坐在海蒂和戴维之间。按照这个限制排布六位人员后，就已经形成闭环，剩余三位家庭成员没有空余位置安排，也就是说依照现有相处条件，这场家庭聚餐注定无法实现全员和睦就餐。

其实想要化解这个难题并不复杂，只需缓和祖母与伊恩叔叔之间的矛盾，让二人能够正常相处即可。调整关系后，依旧保留爱丽丝挨着比尔、比尔挨着祖母的排布方式，再由祖母衔接伊恩叔叔，伊恩叔叔对接海蒂，顺着连线依次安排剩余人员，最后由戴维回到爱丽丝姨妈身旁，就能完成全员无矛盾的落座排布，仅仅新增一条关系连线，难题便能顺利解决。

这类座次排布问题之所以难解，核心原因在于可选排布方案数量极为庞大。示例中部分人员相处限制严格，仅能和两人相邻，尚且容易判断结果；倘若人数扩充至千人，多数人可相邻人数多达四百人，每确定一位就餐人员，后续都会衍生出海量选择，极易陷入繁杂的方案筛选当中。面对这类复杂难题，最便捷的解决方式便是借助计算机运算。

接下来我们追溯计算机理论的起源，艾伦・图灵被公认为现代计算机理论奠基人。1930年代后期，正值二十多岁的图灵提出了图灵机这一理论计算模型，时至今日，世间所有实体计算机的运行逻辑，依旧依托这一经典模型，这也是我日常给本科生授课的核心内容。

在实体计算机诞生之前，图灵便构想设计出这款通用型机器，可通过录入不同指令完成各类不同任务。在这之前，市面上仅有功能单一的专用运算设备，仅能完成固定计算工作，而图灵机打破了这一局限，可灵活切换运算任务，适配多元化运算需求。在各类运算问题当中，最基础的便是仅有是或否两种答案的判定类问题，无需输出复杂结果。

1936年图灵通过严谨论证证实，存在大量仅有是非答案的数学判定问题，这类看似常规的运算问题，依靠任何计算机都永远无法完成求解。这一研究成果彻底颠覆了二十世纪数学界的研究思维，数学研究不再只聚焦于如何解题，而是开始探究问题本身是否具备可解性。

图灵通过具象实例佐证了这一结论：不存在任何一款通用程序，能够检测所有程序在录入指定输入内容后，究竟会正常终止运行，还是陷入无限循环。日常使用电子设备时出现的卡顿卡死、页面加载停滞等现象，从数学理论层面而言便是无法彻底规避的，我们无法编写统一程序提前预判所有程序的运行终止状态。

这个结论听起来难免让人觉得消极，不过后续我们还有更多积极的研究内容。这类无法求解的问题被统称为不可判定问题，依托该结论，学界还推导出了大量同类不可判定难题。

举个趣味实例，卡牌游戏万智牌便属于不可判定问题，该游戏可不断扩充卡牌卡组，对局规模没有上限，从理论层面无法判定对局玩家是否存在必胜策略，这也是学界已经证实的定论。

如今量子计算机备受各界关注，这里补充一项核心理论：图灵机相关定理同样适用于量子计算机。也就是说，传统计算机无法求解的问题，量子计算机同样无法完成求解，二者不存在本质层面的能力差距，后续我会再详细讲解量子计算机的相关应用。

1930年代奠定计算机理论基础之后，一方面学界陆续证实诸多问题均属于不可判定问题，另一方面实体计算机逐步落地投入使用。人们渐渐意识到，即便部分问题具备可解性，若完成运算需要耗费数百年时间，在实际应用中依旧等同于无解。因此运算耗时成为衡量问题求解难度的核心标准。

密码学领域正是依托高难度运算难题搭建安全体系，而在日常科研当中，明确问题的实际运算耗时，也能帮助我们放弃追求完美最优解，转而探寻贴合实际的近似最优解。接下来我们讲解衡量运算难度的具体方式。

以三位数加法运算为例，运算流程仅为逐位对应相加，个位、十位、百位依次运算，进位运算难度极低，几乎可以忽略不计。由此可见，数字加法运算的工作量，仅和数字位数成正比。再回顾多位数乘法运算，运算流程需要将两个数字每一位数值两两相乘，再完成错位叠加求和。由此能够得出，乘法运算的工作量，和两个数字位数的乘积成正比。基于这类规律，学界划分出P类问题，这类问题的运算耗时，能够通过输入规模的多项式函数进行界定。

简单来说，运算耗时仅为输入规模的固定次方级别，加法对应一次方，乘法对应二次方。该概念由杰克・埃德蒙兹于1970年代正式确立，他提出P类问题就是能够在合理时长内顺利完成求解的问题。

很多人会认为多项式函数增长速度同样很快，我们选取运算效率偏低的五次方多项式函数，再对比指数函数 2ⁿ，以计算机每秒完成一千次运算为基准进行测算。当输入规模数值较小时，二者运算耗时差距并不明显；随着输入规模逐步扩大，差距会迅速拉开。输入规模达到三十时，五次方多项式运算需要耗费近七个小时，而指数运算需要耗费十二天；当输入规模扩充至一百时，多项式运算耗时约一百一十五天，指数运算更是需要长达十七个世纪。

由此能够清晰看出，一旦输入数据规模变大，指数级运算耗时会达到完全无法落地应用的程度，即便联动多台设备协同运算也难以落地，若继续扩大数据规模，难度更是会无限攀升。判定问题难度，核心就是测算计算机对应的运算耗时，我们必须依托大规模同类问题进行判定，单一固定答案的问题不具备参考价值。

接下来我们结合实际应用场景，讲解高难度运算问题的实用价值。谈及图灵，除了计算机理论开创者之外，在英国民众心中，他最为人熟知的成就便是破译恩尼格玛密码，这份贡献对二战战局走向起到了至关重要的作用。

恩尼格玛机是二战时期德军使用的核心加密设备，图灵借助自研运算设备成功破解该密码体系。如今这套加密方式早已被淘汰，现代主流加密逻辑依托单向易运算、反向难推演的数学难题搭建而成。

我们以质数相关运算举例，质数是大于1，仅能被1和自身整除的整数，2、3、5都属于典型质数，古希腊时期学界便已证实质数的数量是无穷无尽的。合数则与之相反，存在除1和自身之外的其他因数，例如4、6等数字。

判定小数字是否为质数十分简单，而判定超大数值是否为质数、完成大数质因数分解，却是各类计算设备都难以快速完成的难题。

日常线上金融通信便是依托这一原理搭建安全体系：银行对外公开由两个大质数相乘得出的超大合数，大众利用该公开数值完成信息加密并发送至银行，银行凭借私密的两个质数值，解密读取通信内容，整套加密体系的核心，就是大数相乘运算简单，质因数分解运算难度极高。

再分享一项工业生产领域的实际调度难题：工厂配备三台生产设备，一夜之间积压大量待加工订单，需要在四百八十分钟内完成所有订单加工，规划合理的订单分配方案。面对这类调度问题，行业内普遍采用回溯搜索算法求解，这也是我此前研究人工智能领域时重点钻研的核心算法之一。

算法实操流程为先优先给第一台设备分配加工订单，直至设备工时用尽，再依次分配其余设备订单。若分配方案最终无法完成全部订单加工，就撤销最后一步订单分配选择，重新调整排布方案，反复试错调整，直至匹配出符合工时要求的最优排布方式。

这类算法和大家破解数独谜题的思路高度相似，先暂定答案试算推演，出现矛盾后推翻重来，不断筛选可行方案。无论搭配何种优化策略，核心依旧是不断试错排查，遍历大部分可行方案寻找最优解。

讲解完以上内容，我们正式引入经典的P vs NP难题。P类问题即多项式时间内可求解的问题，也就是现实当中能够高效完成求解的各类问题。NP并非指代无解问题，其全称是非确定性多项式时间问题，通俗来讲，判定类NP问题满足这样一个核心特征：若问题存在可行答案，那么这份答案能够在多项式时间内快速完成核验，但是我们暂时没有高效方式自主推导出这份答案。

所有P类问题都隶属于NP问题范畴，我们既能自主快速求解，自然也能快速核验答案正误。此前讲到的家庭座次排布问题、大数质因数分解问题、工厂订单调度问题，都属于典型的NP问题。我们很难快速自主规划出合理方案，但只要给出现成排布方案、分解结果与调度计划，就能立刻核验方案是否成立。在实际应用当中，绝大多数NP类难题，目前都只能依靠回溯搜索这类试错方式求解，仅能处理小规模简单案例，不存在通用高效的自主求解方法。

2000年，克雷数学研究所为迎接千禧之年，甄选七大顶尖数学未解难题，为每道难题设立一百万美金悬赏奖金，P是否等于NP这一难题便位列其中。该难题直白释义为：倘若一道问题的答案能够快速核验，那么是否必然存在对应的高效解题思路，实现快速自主求解。

截至目前，七大千禧年难题当中，仅有庞加莱猜想已经完成证明，其余难题依旧悬而未决。倘若能够证实P等同于NP，找到通用高效的NP问题求解算法，不仅能够快速核验各类数学证明过程，还能依托计算机自主推导完成数学命题证明，甚至有机会顺势攻克其余六大千禧年难题。

接下来我们讲解NP完全问题的定义：所有隶属于NP范畴的问题，只要找到其中任意一道NP完全问题的多项式时间求解算法，就等同于证实P等于NP，所有NP问题都能实现高效求解。该理论（Cook-Levin定理）由史蒂文・库克与伦纳德・莱文两位学者各自独立证实，在正式定名之前，二人便已经证实了这类核心难题的存在。

现代计算机与复杂性理论奠基人之一高德纳（即唐纳德・克努特），在1974年面向学界征集这类难题的正式名称，最终确定命名为NP完全问题，这个名称偏向专业晦涩，并未达到他的预期，但最终被学界沿用至今。他还曾公开表示，自己深耕相关领域多年，始终认为P等同于NP的可能性微乎其微，甚至公开许诺，除官方百万美金奖金之外，额外赠送一只活火鸡，奖励成功证明该命题的学者。

此前讲到的家庭围桌座次排布问题、工厂生产订单调度问题，都属于典型的NP完全问题，只要攻克其中任意一道难题，就能斩获克雷数学研究所悬赏奖金，证实P与NP等价。而大数质因数分解问题，学界普遍认定其并不属于NP完全问题。

再回到量子计算机的相关应用，1994年彼得・肖尔（Peter Shor）研发出适配大数质因数分解的量子算法。量子计算机可以依托量子比特，同步模拟海量运算设备并行运算，运算效率远超传统计算机。一旦量子计算机技术成熟落地，现有的主流质数加密体系将会彻底失效。

谷歌官方早已发布相关行业预警，明确提及量子计算时代即将到来，各大企业已经着手将电子设备安全加密方式，逐步替换为能够抵御量子攻击的新型体系，并且定下2029年为关键转型节点，足以看出这项技术带来的行业变革迫在眉睫。

不过目前学界尚未研发出能够求解NP完全问题的量子算法，也有相关研究佐证这类难题很难依托量子计算实现高效求解。简单总结来说，量子计算机能够优化部分高难度非NP完全问题的运算效率，但无法撼动P对NP这一核心难题的研究格局。

接下来我结合自身研究方向展开讲解，我此前深耕人工智能领域时，长期研究依托对称性优化搜索算法，以此提升调度排布类难题的求解效率。

图同构问题是我长期钻研的重点研究方向，结合此前讲解的图论基础，图同构问题就是判定两张顶点、边线构成的关系图，抛开顶点命名差异后，二者整体结构是否完全一致。即便两张关系图画法不同、顶点标注名称不同，只要能够一一匹配对应顶点位置，边线连接关系完全吻合，就可以判定两张图属于同构图。

该问题同样隶属于NP问题范畴，他人给出顶点对应关系后，我们能够快速核验判定结果是否正确，但目前依旧没有通用的多项式时间高效求解算法。学界普遍认为该问题不属于NP完全问题，是介于P类问题与NP完全问题之间的中间难度问题，存在极高的实际应用价值，但其具体运算难度至今没有精准定论。

对称性是剖析图同构问题难度的核心切入点，图形对称变换就是在不改变图形整体结构的前提下，调换内部元素位置。部分简易关系图存在明显对称特征，可自由调换部分顶点位置且不改变整体连线结构，固定唯一特殊顶点后，就能快速锁定所有元素排布位置，大幅降低判定难度。

对称性特征同样能够作用于此前讲解的各类实际难题：存在对称特征的家庭人员相处关系图，能够快速判定落座方案是否可行；工时一致的生产订单、规格统一的生产设备，也能依托对称特征简化调度排布流程。反之，打破对称特征，就会直接提升问题求解难度。

图同构问题的求解难度，和图形结构拆分形式、顶点边线分布特征息息相关。结构拆分清晰、顶点连接边线数量差异化明显的图形，同构判定难度更低；整体结构高度统一、对称特征极强的图形，判定难度会大幅提升。1980年代有学者证实，攻克图同构问题，核心就是探寻单一关系图的所有对称变换形式，重点攻克原始群结构下的图形对称问题即可。

2016年巴比（Babai）取得该领域重大研究突破，证实图同构问题能够借助拟多项式时间算法完成求解。拟多项式函数的增长速度，介于普通多项式函数与指数函数之间，运算耗时远低于回溯搜索这类指数级运算方式。后续还有学者持续优化算法参数，不断压缩拟多项式运算的耗时系数，如今缩减核心系数数值，依旧是该领域极具研究价值的前沿方向，若系数能够无限趋近于1，该算法就会无限贴近标准多项式算法。

最后我们总结攻克千禧年难题、赢取百万奖金的两种研究方向。

其一，证实P等同于NP，只需找到任意一道NP完全问题的多项式时间通用求解算法即可。一旦完成证明，不仅能够实现大数快速质因数分解，摆脱对量子加密算法的依赖，交通调度、日程规划、资源统筹等所有NP类实际难题都能实现高效求解，彻底改变当下的运算科研格局，甚至顺势攻克其余六大千禧年数学难题。不过这项研究成果一旦问世，势必会影响全球各类安全加密体系，相关领域相关机构也会高度关注这项研究进展。

其二，证实P不等于NP，只需证明任意一道NP范畴内的问题，不存在任何多项式时间高效求解算法即可。目前绝大多数数学界学者都更倾向于认同这一结论，这也是当下学界的主流观点。多年以来，无数研究者尝试为NP完全问题搭建高效算法，最终均以失败告终。而目前最大的研究困境在于，学界依旧没有成熟严谨的论证方法，能够直接证实一类问题不存在高效求解方案，想要完成这项证明，还需要诞生堪比图灵机理论的全新颠覆性数学思想。

大家也可以选取自己感兴趣的中间难度数学问题展开研究，例如深入钻研图同构问题，尝试论证其不存在多项式时间求解算法，同样能够完成相关命题证明。

我的本场讲座内容到此结束，再次感谢各位的认真聆听。

Q&A 问答环节

主持人：

非常感谢科尔瓦教授带来这场精彩绝伦的讲座，相信在场所有人都收获满满。接下来我们进入问答交流环节。正如教授所言，倘若在座各位已经构思出P对NP难题的证明思路，还请谨慎斟酌。线上观看直播的观众依旧可以扫描二维码提交问题，现场观众举手即可，我们会依次传递麦克风收集问题。

现场第一位提问者：

您好，非常感谢这场干货满满的讲座。我并非专业数学研究者，目前正在为英国皇家艺术学会撰写相关文稿，该学会拥有三万余名会员，当下最大的难题就是搭建完善的会员社交联络体系，为此我查阅了大量同类高难度统筹问题相关资料。在查阅资料的过程中，我接触到卡尔・弗里斯顿依托贝叶斯推理搭建的数学推演理论，其论文当中的专业代数推导内容我无法自主解读，但借助人工智能工具，我能够梳理论文自然语言核心观点，再拆解理解代数推导逻辑，重新研读专业学术论文。我想请教您，站在专业数学研究者的角度来看，人工智能辅助解读学术内容、赋能人类科研思考的模式，是否会从根本上改变整个数学领域的研究思维与发展格局？

答：

我由衷希望人工智能能够打破大众对数学的刻板印象，消解普通民众对数学的畏惧心理。日常社交当中，每当我告知他人自己是数学研究者，绝大多数人的第一反应都是坦言自己学生时代数学成绩不佳，倘若人工智能能够改善这一现状，便是极具价值的积极作用。

在学术证明研究领域，目前仅顶尖专业科研团队能够借助定制化人工智能工具辅助推导证明；普通本科生借助通用人工智能完成课程习题解答，得出的答案依旧存在大量逻辑漏洞。

人工智能擅长文字梳理、文献检索工作，能够快速检索数十年前冷门学术论文当中可用的引理结论，实现学术观点整合归纳，这也是目前人工智能在数学领域最核心的实用价值。

但通用人工智能尚不具备严谨自主逻辑推演能力，仅能整合现有文字内容输出观点，暂时无法独立攻克 P 对 NP 这类核心数学难题。

整体而言，人工智能能够成为数学科普、学术调研的优质辅助工具，但短期内依旧无法取代人类学者的核心科研思维。

现场第二位提问者：

您好，听完本次讲座我有一个疑问，哥德巴赫猜想、孪生素数猜想这类经典数论未解难题，是否能够套用今晚讲解的 P与NP 相关理论进行研究分析？

答：

这类数论猜想和我们今晚探讨的判定类是非问题不属于同一范畴，这类猜想是针对无穷多自然数提出的整体性命题，无法直接划入 P 类与 NP 类问题的划分体系当中。

二者唯一的关联点在于，倘若证实 P 等同于 NP，人类能够依托计算机快速完成数学命题证明推导，届时便有机会借助机器运算完成这类数论猜想的完整证明，但这套理论无法直接用于推进猜想研究进程。

不过当下已有学者依托超大范围计算机辅助运算，证实了弱版哥德巴赫猜想，也就是奇数三素数之和定理。研究者借助计算机完成海量数值验算，划定小范围数值成立依据，再通过纯数学推导证实超大数值区间内命题成立，完成整套证明流程。这类计算机辅助证明，依托的是固定单次运算程序，并非可反复通用的多项式算法。

现场第三位提问者：

您好，我了解到有相关研究证实，菌群能够自主求解旅行商（TSP）这类统筹规划难题，想请教这类依托自然生物规律形成的运算模式，是和大数分解问题一样属于中间难度问题，还是能够成为攻克指数级难度难题的全新思路？

答：

旅行商问题是典型的NP完全问题，想要高效求解这类难题，各类新型运算模式的核心逻辑基本都是大规模并行运算，依托海量运算单元同步试错推演，依靠数量优势压缩整体运算时长。这类自然生物形成的自主统筹模式，能够快速处理小规模简易案例，但无法形成通用规律适配所有场景，依旧存在部分特殊案例难以顺利求解。我对菌群相关专项研究了解不多，但从复杂性理论角度来看，这类模式仅能优化局部运算效率，无法从根本上解决NP完全问题的核心研究困境。

线上观众提问一：

能否在讲座内容当中补充提及埃达・洛夫莱斯？

答：

非常乐意补充介绍。埃达・洛夫莱斯是计算机发展史上不可或缺的先驱人物，她最早为查尔斯・巴贝奇设计的分析机编写运算程序，这份研究成果也成为图灵机理论诞生的重要思想铺垫。她的研究成果拥有极高的历史地位，理应收获更多学界赞誉，不过其研究聚焦于早期程序编写，尚未涉及运算时长、问题难度判定等相关研究内容，因此本场讲座未做重点讲解，非常感谢这位观众的提醒。

线上观众提问二：

您提到大数质因数分解不属于NP完全问题，倘若证实P等同于NP，是否所有NP范畴内的问题都会成为NP完全问题？

答：

没错，一旦证实P与NP完全等价，所有NP问题的求解难度将会趋于统一，自然不再区分中间难度问题与NP完全问题。在目前未完成证明的前提下，学界依旧将大数分解、图同构这类问题划定为中间难度问题，难度介于标准P类问题与NP完全问题之间。

现场第四位提问者：

您好，抛开量子计算机不谈，依托当下高速迭代升级的通用人工智能，未来是否会出现人工智能自主破解 P对NP 难题，却刻意隐瞒研究成果的情况？

答：

从技术层面来讲这种情况基本不可能发生。当下主流生成式人工智能的核心优势集中在学术文献检索、观点整合梳理、科普内容撰写等领域，能够快速挖掘冷门学术成果、整合多方研究思路，这也是目前人工智能在数学领域最核心的突破点。

但这类人工智能缺乏严谨自主逻辑推导能力，无法自主搭建完整的数学证明体系，甚至无法自主判别自身输出内容的正误，所有和数学证明相关的输出内容，都必须依靠专业研究者逐一核验、修正。当下人工智能仅能作为科研辅助工具，距离自主攻克顶尖数学核心难题，还有极为遥远的距离。

主持人：

由于时间有限，本场公开问答环节到此结束。大家若是还有其余问题，可短暂停留现场，和教授私下交流探讨。再次感谢各位莅临格雷沙姆学院参与本次学术活动，感谢伦敦数学会的通力合作，也再次由衷感谢科尔瓦・罗尼 - 杜加尔教授带来这场极具深度与趣味性的精彩讲座。

参考资料

https://www.gresham.ac.uk/watch-now/hard-complexity

https://www.youtube.com/watch?v=y9G_8_JItdc

小乐数学科普近期文章

版权声明：本文首发于微信公众号“zzllrr小乐”的专栏《小乐数学科普》。欢迎个人转发。如需转载，请在“zzllrr小乐”公众号后台回复“转载”，还可通过公众号菜单、发送邮件到zzllrr@gmail.com与我们取得联系。相关图文音视频内容默认遵守CC BY-NC 4.0知识共享协议，未获作者和译者授权，禁止用于营销宣传和商业目的。

·开放 · 友好 · 多元 · 普适 · 守拙·

让数学

更加

易学易练

易教易研

易赏易玩

易见易得

易传易及

欢迎评论、点赞、在看、在听

收藏、分享、转载、投稿

查看原始文章出处

点击底部一起捐

助力腾讯公益

点击zzllrr小乐

公众号主页

右上角

置顶★加星

数学科普不迷路！