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

禁止部分比较的排序,几乎一样快

要通过两两比较把n个元素排好序,大约n log n次比较既是必要的,也是足够的。但这假设任意两个元素都可以比较。

往往并非如此。作者借用了2011年一篇论文中的例子:几位求职者申请同一份工作,每人都有推荐人。只有当某位推荐人同时认识两位求职者时,这两人才能相互比较。允许的比较构成一个网络,即一张图:每个元素是一个点,每个允许的比较是一条连线。真正的顺序是隐藏的,但可以保证图中包含它,表现为一条把每个元素与下一个元素相连的路径。问题是:要恢复这个顺序,需要多少次比较?这就是广义排序。

常用技巧为何失效

经典算法依赖于选择的自由。快速排序(QuickSort)选一个“基准”(pivot),并将它与大多数其他元素比较,但在任意一张图中,可能没有哪个元素与大多数其他元素相连。归并排序(MergeSort)把元素分成若干组,分别排序,但一个组本身可能无法排序:在最终顺序中相邻的两个元素,在组内未必相连。更根本的是,普通排序总有一个可用的比较能排除相当一部分可能的顺序;而在比较受限时,可能一个这样的比较也没有。

进展缓慢。2011年,Zhiyi Huang、Sampath Kannan和Sanjeev Khanna找到了一种使用约n¹·⁵次比较的方法(不计对数因子),此后对于任意图,这一界限一直未被打破。他们甚至问过,这个问题是否在根本上比普通排序更难,需要n的某个大于1的幂次。

先预测,后修补

纽约大学的Sanjeev Khanna、哈佛大学的Aaron Putterman和同样来自纽约大学的Junkai Song如今回答了这个问题:答案是否定的。他们的随机化算法在任意图上平均用约n log⁴ n次比较完成排序——只比普通排序多几个对数因子。而且,他们写道,它“相对简单”。不过,这一优势只是理论上的:证明中的常数极其巨大(例如2³²这样的因子),因此只有当n非常大时,这一优势才会显现。

它建立在一个已知结果之上:如果有人给你一个关于每条连线方向的猜测,其中有w条是错的,那么用约n log n + w次比较就能恢复顺序。于是任务变成:用很少的比较,产生一个错误很少的猜测。关键步骤如下:

  • 粗略的初始猜测。随机抽取一部分相连的元素对进行比较,然后选取任意一个与这些结果一致的顺序。它会犯许多错误,但不会太多。
  • 隔离错误,而不是修正错误。算法不去纠正错误的猜测,而是找出图中错误比平均更密集的部分,把它们放在一边。每一轮都会使剩余错误的期望数量减少到原来的四分之一。
  • 稍后再处理。被放在一边的连线留到后面的阶段处理。每个阶段至少解决仍待处理连线的一半,因此对于100万条连线,大约二十个阶段就够了。

借助机器找到的证明

论文中的人工智能使用披露异常详细。它写道,ChatGPT 6-Astra“在证明改进的界限时必不可少”。一个模型先找到了一个使用约n¹·³³次比较的算法,随后陷入停滞。作者把它推进到n¹·²;之后,在几周内经过数十次提示,模型陆续找到了一系列改进——n^(10/9)、n^(17/16)、n^(19/18)——最终得到了近线性的算法。作者补充说,尚不清楚他们自己的中间步骤对最终的发现是否必不可少。

仍未解决的问题

这一结果计算的是比较次数,而不是计算时间:按目前的表述,该算法不能在多项式时间内运行,而2011年的方法可以。作者列出了三个未解问题:剩下的对数因子能否去掉;不使用随机性的算法能否做得一样好;以及高效的算法能否达到同样的比较次数——甚至能否突破n¹·⁵。