计算机科学中一道1962年的壁垒被打破

哈密顿回路是在网络中走一圈、恰好经过每个点一次并回到起点的路线。在有向网络中，每条连线都是一个只能沿一个方向通行的箭头，就像单行道。这一问题的加权版本就是非对称旅行商问题。

判断这样的回路是否存在，是一个教科书级的难题。1962年，Richard Bellman，以及独立研究的Michael Held和Richard Karp，提出了动态规划算法，对于含n个点的网络，可在大约2ⁿ的时间内求解（忽略只按多项式增长的因子）。六十多年来，对于一般的有向网络，没有人能从根本上做得更好。

它的无向“表亲”早已被攻克

对于连线为双向的网络，Andreas Björklund于2014年用一个运行时间为1.657ⁿ的随机算法突破了这道壁垒；据论文介绍，这项工作使他获得了2016年EATCS–IPEC Nerode奖。它至今仍是一般无向网络已知最快的算法。对于有向网络，进展只出现在特殊情形中——二部网络、每个点连线较少的网络——或者依赖于一个未经证明的假设，即Strassen渐近秩猜想。

新的上界

东京大学的Tomohiro Koana和东京CyberAgent公司的Soh Kumabe，如今给出了一个随机算法，可在如下时间内判定有向问题：

O((375/196)ⁿ) = O(1.9133ⁿ)**。

对于一般有向网络，这是自1962年以来指数底数的首次改进。

用奇偶来计数

难点十分微妙。对回路数做模2计数——只知道其数目是奇数还是偶数——此前已经可以在低于2ⁿ的时间内完成。但一个非零的偶数个回路，看起来和零完全一样。经典的补救办法是给连线赋予随机权重，使得在某个总权重下解变得唯一（即隔离引理）；但快速的奇偶计数方法无法处理权重。

作者的方法，用通俗的话来说：

1. 猜出回路中的一个箭头，转而寻找一条从该箭头一端出发、经过所有点到达另一端的路径。
2. 以1/50的概率随机删除每个箭头。
3. 在每个点上，把进入该点的箭头分成三个组，并把每个保留下来的箭头复制到一个随机的非空组集合中。
4. 如果存在环游路线，那么至少有(49/50)ⁿ⁻¹的概率，可以为每个点选出一个组，使有效路径的数目为奇数。
5. 给每个组——而不是每个箭头——赋予随机权重。这样隔离技巧就能奏效了，大约重复(50/49)ⁿ次就足够。
6. 每次重复都在(15/8)ⁿ的时间内计算出每个总权重下的奇偶计数，所用方法是Björklund、Kaski和Koutis提出的矩阵行列式求和，以及Arvind和Guruswami也使用过的一种随机“线性化”。

两者相乘：(50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ。

由机器生成的证明

论文末尾附有一份关于生成式人工智能的声明：ChatGPT 6 Astra生成了主定理的证明，并协助起草了论文。作者提供了中间命题的表述，这些命题对模型的原始解法给出了组合学解读；随后他们核查并修改了全部内容，并承担全部责任。

这一结果是理论性的——没有运行任何程序——而且算法是随机的，在两个方向上都有很小的出错概率。在单行道的1.9133与双向道路的1.657之间，仍有一道宽阔的鸿沟有待填补。