MIT教授带博士生3天赶出95页论文

7年研究心血，传闻马上要被AI抢先。 MIT数学副教授收到风声后，立刻带着两名中国博士生，用时3天赶出95页论文，赶在AI之前公开发布。 过去七年，明泽一直在研究与唯一博弈猜想有关的问题。 就在几个月前，他与两名研究生费雨缪、王硕完成了一项重要证明。 成果已经有了，论文却还在写。 如果OpenAI先公布成果，他们的工作仍然成立，却会被更轰动的新闻淹没。 三人决定提前公开手稿。 9月14日，一篇95页的预印本出现在计算复杂性电子论坛（ECCC）上。

10月6日，OpenAI果然公布了一批数学研究结果，其中包括唯一博弈猜想以及相关的2-to-1博弈猜想。 AI交出的结果在结论强度上比明泽团队的4-to-1博弈猜想成果更强。 这场没有简单的输赢。 2002年，苏巴什·霍特提出了唯一博弈猜想。 想象一座城市要给地图上的许多区域涂颜色。 相邻区域之间都写着规则：如果这边选红色，那边就得选蓝色； 如果这边选绿色，那边则要选黄色。 每条连接都有自己的规定。 规则少时，试几次就能找到合适的涂法。 规则成千上万、彼此牵制时，找出满足最多规则的方案，需要难以想象的计算量。

四个顶点可以分别染成红色、蓝色和绿色，每条边两端的颜色搭配都符合这条边自己的规则。 霍特猜测，对某些经过特殊构造的问题，答案仍然是否定的。 唯一博弈中的“唯一”指的是，一条规则里，一侧的颜色定了，另一侧该涂什么也就唯一确定。 所谓高效，是指区域数量增加时，计算时间只温和增长，而不是像逐个试遍那样暴涨成天文数字。 而NP困难，粗略理解，就是如果能高效解决这类问题，便能高效解决NP中所有公认困难的计算问题。 这一猜想意义深远，因为很多现实任务最终都要在互相冲突的条件下寻找较好的方案。

1995年，两名研究者为最大割问题提出了一种近似算法。 最大割问题的双色网络示意图。 若唯一博弈猜想成立，在通常的计算复杂性假设下，没有高效算法能保证做得更好。 这个看似随意的数字，恰好就是理论极限。 2018年，明泽与霍特等人证明了与唯一博弈密切相关的2-to-2博弈猜想的一个版本。 到2025年，他在MIT有了两位年轻合作者。 费雨缪（Yumou Fei）本科毕业于北京大学数学科学学院。 王硕（Shuo Wang）的本科则在上海交通大学ACM班度过，后来进入MIT数学系攻读博士。

2025年，明泽向两名学生提供了两个可选课题，他们选了与2-to-1博弈猜想有关的方向。 这次，他们希望证明一种更强的“完全满足”版本（即具有“完美完备性”的版本）：即使所有规则都能同时满足，想高效地找到一个满足哪怕一小部分规则的涂法，仍然是NP困难的。 两名学生找到了一种新的纠错码构造。 这个思路很有希望，偏偏无法与证明所需的其他技术顺利兼容。 到2026年4月，他们终于找到办法，把几次失败中积累的思路和新的纠错码结合了起来。

不过，最后证明的并不是最初瞄准的2-to-1版本，而是规则更宽松的4-to-1版本——一边涂了某种颜色，另一边可以有四种选择。 但这个结果依然足够强，可以像垫脚石一样，推出一个困扰学界多年的图着色难题的答案。 这里的“图”，指由点和连线组成的网络，比如把人看作点，把好友关系看作连线。 给图着色，就是给每个点涂一种颜色，规定是有连线的两个点不能同色。 假如数学家告诉你，某张图只用三种颜色就能涂好。 可真要找出这种涂法，计算机往往束手无策。 那就退一步，多给几种允许的颜色，十种呢？ 一百种呢？

颜色越多，腾挪的空间越大，直觉上应该越来越容易涂好。 明泽团队用数学证明，事情没这么简单。 目前已知的高效方法，需要的颜色数都会随着图的变大而增加。 即使明知三色涂法存在，额外多给多少种颜色都不管用。 十种、一百种、一百万种都一样。 只要这个数目是事先定好的，不随图的规模增长，找出合法涂法就依然是NP困难的。 这对算法设计有直接意义。 许多优化方法的思路是多给一些资源、放宽一些条件，以换取更快的计算速度。 这项证明表明，至少对这类问题，这种“以宽换快”的办法存在严格的理论上限。