Nature：DeepMind大模型突破60年数学难题，解法超出人类已有认知

来源：量子位

图片来源：由无界 AI生成

用大模型解决困扰数学家60多年的问题，谷歌DeepMind最新成果再登Nature。

作者之一、谷歌DeepMind研究副总裁Pushmeet Kohli表示：

训练数据中不会有这个方案，它之前甚至根本不为人类所知。

这项技术名为FunSearch，其中的Fun是函数（Function）一词的简写。

利用大模型解决长期存在的科学难题，产生以前不存在的可验证且有价值*的新信息。

在Nature论文配套的新闻解读中，DeepMind负责人称“我们使用大模型的方式是当做创造力引擎”。

这是第一次有人证明基于大模型的系统可以超越数学家和计算机科学家的认知。
它不仅新颖，而且比当今存在的任何其他东西都更有效。

针对这项成果，有网友感慨：

如果这是真的，那可是人类自 火之后最重要的发现了。

那么，FunSearch都解决了哪些问题呢？

找到NP-hard问题更优解法

DeepMind具体展示了两类问题，它们都属于NP-hard问题。

在学界看来，没有而且可能永远也不会有一种算法能在所有情况下都在多项式时间内找到NP-hard问题的精确解。

面对这样的问题，研究者通常会寻找近似解或适用于特定情况的有效算法。

具体到FunSearch，它解决的第一类NP-hard问题是Cap set问题，是上限集问题的一种，它的描述是这样的：

在一个n维空间中的每个维度上都有等距的n个点（共n^n个，比如3维就是3*3*3），从中找出尽可能多的点构成一个集合，要求集合中任选3个点均不共线，这样的集合中最多有多少个点？

如果看上去有些难以理解，不妨再了解一下Cap set问题的前身——上世纪70年代遗传学家Marsha Falco发明的一套卡牌游戏。

这套卡牌游戏中一共有81张牌，每张牌中都有1至3个颜色图案，同一张牌中的图案颜色、形状和阴影完都全相同。

这套牌一共有3种颜色、3种形状和3种阴影，加上图案数量的不同，一共有3*3*3*3=81张，玩家需要翻开一些纸牌，找到3张牌的特殊组合。

如果把这种“特殊组合”的具体方式用离散几何形式进行表达，就得到了Cap set问题。

Cap set问题同样诞生于70年代，由牛津大学数学家Ron Graham提出，而第一个重要结果直到90年代才出现。

2007年，陶哲轩在一篇博客文章中提到，这是他最喜欢的开放式数学问题。

在FunSearch出现之前，Cap set问题最重大的突破是美国数学家Jordan Ellenberg和荷兰数学家Dion Gijswijt于2016年提出的。

通过多项式方法，Ellenberg和Gijswijt将n>6时（n≤6时可精确找到最大集合）此类问题解的上确界缩小到了2.756^n。

同样在n>6时，下确界的较新数字则是2.218^n，由布里斯托大学博士生Fred Tyrrell在2022年提出。

但这个下确界仅仅存在于理论上——当n=8时，人类能构建出的最大集合中只有496个点，而按照Tyrrell的结论，点的数量应不少于585.7个。

FunSearch则将集合规模扩大到了512个点——虽然和理论值依旧存在差距，但仍被视为20年来在此问题上最重大的突破。