2021年10月10日上午十点，国家特聘专家，乌镇智库理事长，图灵算力研究院院长张晓东教授应计算机科学与技术学院邀请，在吉林大学中心校区计算机楼A521报告厅作了题为“计算复杂性50年：王浩与计算理论”的专题报告，这是本科生综合素质提升计划系列报告的第五场，报告由计算机科学与技术学院副院长张永刚教授主持，计算机学院、软件学院共30余名本科生参加了此次报告会。

张晓东教授（笔名，尼克）。国家特聘专家，乌镇智库理事长，图灵算力研究院院长。毕业于天津大学，中科院和美国麻省大学。早年在哈佛从事生物信息学研究，后在HP负责互联网支付项目。曾连环创业，并担任VC合伙人和上市公司独立董事，所著《人工智能简史》获吴文俊奖和中华优秀出版物奖。

从1971年Cook文章发表日开始算，到2021年计算复杂性理论正好50岁。今年又恰逢Cook的导师王浩诞辰100年，本次报告中张晓东教授为大家回溯计算复杂性的起源，并力图梳理王浩和这门学科的关系。本次报告主要包括三方面内容：

首先，是梳理计算复杂性的源头。早在20世纪30年代就有数学家提出“计算复杂性”的概念，到20世纪50年代，纳什提出了多项式复杂性和指数复杂性的区别，他推测指数复杂性对加密算法是有用的。Cobham在1964年的科学哲学大会上发表过计算复杂性相关的文章。但那个时期的计算复杂性并未得到充分的重视，计算机科学作为一门独立的学科刚刚开始，数学系的主流还没把计算理论当回事。

Cook对计算复杂性的贡献是他在1971年证明了命题逻辑的可满足性问题（SAT）是NP完全的。用命题逻辑来描述非确定图灵机多项式时间运行的所有可能状态，他的论文题目和定理证明相关。Cook的工作影响了很多人，包括图灵奖获得者Leslie Valiant。数学家斯梅尔对他工作的评价是：计算机科学给数学的礼物。

再到王浩：Cook用到的方法受到王浩启发，cook自己也承认他对NP完全问题的结论与王浩的AEA非常类似，他的文章里也引用了王浩的一些逻辑演算。张教授认为，在可计算性理论和计算复杂性理论之间，王浩起了承上启下的作用。他被忽视，有外在的原因：图灵和Cook影响过于深广；另一方面，也有内在的原因，王浩晚年转向哲学，对计算理论兴趣不大。但是王浩对计算复杂性的贡献不能被淹没在历史的河流中，年轻的学子应该知道他在这个领域中做出的贡献。

张教授的报告风趣幽默、内容扎实，让在场听众了解了计算复杂性这一学科的发展历程和对这门学科做出过贡献的伟大科学家们，一门学科的发展是无数人共同努力的结果，无论成就大小，所有做过贡献的人都值得被铭记。计算机科学与技术学院副院长张永刚教授代表吉林大学计算机学科对张教授拨冗前来进行本科生综合素质提升指导表示了感谢。本次本科生综合素质提升系列报告是吉林大学本科生培养和素质提升的重要组成部分，后续将继续举办其他本科生综合素质提升计划系列报告。

计算机科学与技术学院