计算机与人工智能预印本理论阅读 1 分钟

寻找团的速度极限在40年后被打破

设想一个有n个人的社交网络。其中是否存在一个由k个人组成、彼此全都认识的群体?计算机科学家把这样的群体称为k-团(k-clique),寻找它是一个经典问题,有无数应用。朴素的方法是检查每一个可能的k人组合,大约有n^k个——对于大型网络来说毫无希望。

1985年的技巧与一项长期挑战

40多年前,Jaroslav Nešetřil和Svatopluk Poljak找到了一条捷径。他们把寻找k-团的问题转化为在一个更大的图中寻找三角形,而后者又可以通过矩阵乘法——即大型数字表格的相乘——来完成。代价取决于ω,即矩阵乘法的指数:他们的方法大约需要n^(ωk/3)步。没有人确切知道ω的值。它至少为2,文章引用了最近的一个上界9/4。

1985年那个方法的指数从未被超越。2004年,Gerhard Woeginger向研究者发起挑战,要求对某个固定的k做得更好;二十多年就这样过去了。与此同时,k-团假设(k-Clique Hypothesis)——即n^(ωk/3)基本上就是可能达到的最好结果——成为了“细粒度复杂性”(fine-grained complexity)的一块基石。研究者用它来论证,许多其他问题,从文法解析到压缩数据的分析,同样无法更快地求解。

一个移动的靶子

反驳这一假设有一个特殊的困难。它预测的代价取决于ω,而ω是未知的。一个击败了当今ω最佳值的算法,如果日后有人找到更快的矩阵乘法,就可能不再能击败这一假设。

MIT的Virginia Vassilevska Williams和特拉维夫大学的Or Zamir绕开了这个问题。他们证明,对于每一个足够大的k,都可以在大约n^((ω/3 − c)k)步内找到——甚至计数——k-团,其中c是一个既不依赖于k、也不依赖于ω的正常数。这种节省是相对于ω的真实值来衡量的,无论它最终是多少。即使ω = 2——可以想象的最佳情形——它依然成立。

折叠一个楔形

该方法的核心涉及九个顶点的模式。标准做法是把它们分成三组、每组三个,然后把三个巨大的矩阵相乘。作者着眼于一个楔形(wedge)——共享一个顶点的两条边——并在其中两个矩阵之间插入一张不改变任何东西的表格:单位矩阵。然后,他们把这个单位矩阵写成少数几个“交换”(swap)之和,每个交换都把楔形的两条边合并为一条,再加上一个低秩的余项。

这些交换给出边更少、更简单的模式,再用同样的方法处理;一个九顶点模式最多有36条边,因此递归会终止。低秩余项则缩小了需要相乘的矩阵。正是把这一技巧同时应用于两个分开的楔形,才使得即使在ω = 2时也能保留增益。于是,任何是九的倍数的k都可以被分成九个块。

真实存在,但微乎其微

作者没有给出增益的具体数值。他们形容这些常数的范围是“从不加优化时的微不足道,到经过大量优化后的微小”。重点不在于实际的速度:而在于一道被人们相信了几十年的壁垒并不存在。

其影响超出了团的范畴。对于Max-Cut和Max-2-SAT这类困难的优化问题,原本对n个变量大约需要2^(ωn/3)步的精确算法,如今也获得了更小的指数。计数任意固定小图的副本数量也是如此。

AI做了什么

在一个专门的章节中,作者描述了他们如何与ChatGPT-6合作,使用的是它的公开网页界面。从他们自己关于五人团的想法出发,并借助OpenAI最近一项反驳另一个猜想——指数时间假设(Exponential Time Hypothesis)——的成果,该模型为5-团找到了第一个复杂的改进。随后,作者在AI的帮助下,把它提炼成了证明核心中的代数分解,他们认为这部分“几乎纯粹是AI的贡献”。他们说,围绕它构建的算法框架主要是他们自己的。

有一点评论格外引人注目。作者指出,AI生成的晦涩证明很难被人类读懂——而他们“印象深刻的是,这些证明对AI本身来说也很难理解”。