挑出和为目标的数，几乎和读一遍一样快

这是一个人人都能说清楚的谜题。你有一串整数——比如3、9、14、20——和一个目标值，比如23。你能否从中挑出一些，使它们的和恰好等于目标值？（这里可以：3 + 20或9 + 14。）这就是子集和问题（Subset Sum），计算机科学中最基本的问题之一。论文称它为一个基本的NP完全问题——这类问题以难以精确求解而著称。

不过，这里有个漏洞。如果数字不太大，巧妙的算法的运行时间就取决于数字的大小。经典方法由贝尔曼（Bellman）在1957年提出，耗时与数字个数n乘以目标值t成正比。此后，算法不断改进：

• 皮辛格（Pisinger，1999年）：与n × N成正比，其中N是最大的数；
• 布林曼（Bringmann，2017年）：约为n + t；
• 几个团队（2021—2024年）：约为n + N^(5/3)，然后是n + N^(3/2)。

终极目标是大约n + N的运行时间——比读一遍输入多不了多少。该领域的研究者称之为这一系列工作中“最关键的公开问题”。

离目标只差一根头发丝

中国浙江大学的Lin Chen、Yuchen Mao和Guochuan Zhang给出了一个运行时间为n + N^(1+ε)的算法，其中ε可以是预先固定的任意小正数——0.1、0.01、0.001。该算法是确定性的，允许负数和重复值，并附有数学证明。作者称这一运行时间为近乎最优。

这一结果可以推广到向量：挑选若干项，使多个和同时达到各自的目标，对d个坐标而言耗时为N^(d+ε)。这又回答了几个团队提出的关于整数规划的问题的一部分——即为变量有界的方程组寻找整数解。论文明确推导出了两个推论：把一组数分成和相等的两半，以及在两台相同的机器之间尽可能均匀地分配任务。

把数字提升到更高维度

关键想法是几何性的。人们早已知道，当数字稠密、且目标值位于可能和的范围内部时，这个问题很容易。作者的观察是：一个稀疏的数集，从更高的维度看去，可能是稠密的。

他们举的例子是集合{11, 12, 22, 24}。把11和22写成沿第一条轴走一步和两步，把12和24写成沿第二条轴走一步和两步。这样，所有可能的和就填满了一个4×4小方格中的每一个点。但若把这个方格压回一条直线——通过计算11x + 12y——这些和就会形成七个彼此分开、中间有空隙的簇，散布在0到69之间。这些空隙是投影造成的假象；在二维中，结构很简单。

该算法利用加性组合学的结果，为任何输入构造这样的高维坐标。在“被填满”的区域内，答案唾手可得。只有边缘附近的一个狭窄区域需要真正花功夫，算法把它拆分成更小的问题并递归求解。每一轮都会大幅缩小这个区域，而新增的维度始终只有常数个。

证明是如何完成的

论文开篇有一段“AI免责声明”。作者自己设计了主要的证明路线，其基础是他们最近关于该问题稠密、多维版本的工作。随后，他们用一个AI模型GPT Astra Ultra把这些想法变成完整的数学证明。模型在几个引理上卡住了，这些引理借助作者的想法得以解决；一份公开的研究笔记记录了这些对话。基本的随机化算法完成后，模型“在没有作者任何指导的情况下”把它推广到了确定性和多维版本。模型还起草了论文，而且据作者介绍，它用证明助手Lean 4中的证明验证了论文的主要结果。作者对内容承担全部责任。

还没到终点线

指数是1 + ε，而不是恰好为1，并且隐藏的常数会随着ε缩小而增大；对维数的依赖也没有经过优化。作者自己也形容这个算法“相当复杂”。这篇论文是理论性的：没有报告任何实现或基准测试。