复杂度不低于Ω(log²k)

雷西 发自 凹非寺

量子位 | 公众号 QbitAI

三十多年来，在线算法一直被科学家寄予厚望，但一篇论文的诞生让它走下了神坛。

它的目标，简单来说就是在没有完整数据的情况下，通过有限的信息提前找到最佳策略。

在我们的生活中，例如股票市场的即时交易分析，还有导航路径的实时规划，都有在线算法的身影。

不过没有完整数据，就意味着性能将受到限制；因此科学家们一直期待它能突破数据的桎梏，达到更高的效率。

然而就在最近，来自微软研究院、牛津大学等机构的研究人员在进行了一场实验之后发现，这种算法的复杂度远远超过了人们的期待。

他们也凭借着这篇论文，在今年的计算理论顶会STOC上获得了最佳论文奖。

那么，他们获奖的这项研究，具体说了些什么呢？

科学家们的“30年期待”

这里我们需要先来了解一些背景知识。

和在线算法相对的，还有离线算法，它在开始处理之前需要先接收到所有的输入数据。

由于预先掌握了完整数据，在同等的数据规模下离线算法显著快过在线算法

想象一下，现在要从一系列数字中找出最大值，第一种情况是直接知道所有数字，另一种是比较完前面的数才知道后面的数字是多少，显然第一种情况的速度更快。

于是离线算法的性能被看作是一个标杆，并衍生出了“竞争比”的概念。

而在过去的30多年里，在线算法曾一度被寄予竞争比接近1的厚望。

具体的体现是，关于在线算法，学界有一个经典问题，叫做k-server问题。

k-server问题可以这样来描述：

给定一个度量空间和位于该空间指定位置的k个服务器，在该空间的不同位置中会出现一系列请求。

对于每个请求，都必须选择一个服务器来响应该请求。

如果服务器已经在请求的位置，它可以立即响应；否则，它必须移动到请求的位置。

而k-server问题的最终目标，是将所有服务器移动距离的总和最小化。

举个例子，在一公路旁有若干家餐馆，路上有k个空闲的外卖员，这些餐馆可能随时需要外卖员上门取餐，此时外卖员的调度就可以看做是一个k-server问题。

而在这个过程当中，无论是系统还是外卖员在真的接到订单之前都不知道订单出现的时间和位置，此时的问题是如何将所有外卖员取餐所走的路程之和最小化。

直到这篇论文发表为止，长达30多年的时间里，在线算法一直被期待在解决所有k-server问题时，复杂度都不超过Θ(log k)。

（其中Θ表示渐进紧确界，可简单理解为数量级相同）

但这篇论文的出现，让这个期待被打破。

那么，作者又是如何把这个期待证伪的呢？

复杂度远超预期

注：本节中的对数符号log，如无特别说明，底数为2

递归构建图度量空间

为了探究k-server问题的复杂度，作者构建了一个递归定义的图度量空间（本质上也是k-server问题）。

作者首先构造一个简单的度量空间M(0)，然后把多个M(0)按照循环的方式连成一个环M(1)，然后把多个M(1)连接成M(2)……以此类推，最终形成了一个可以分割成对称的子结构的空间。

在这个度量空间上作者设计了一个随机请求序列ρ，它会在对称子结构之间交替选择请求点，迫使在线算法在子结构间频繁移动，而最优算法是固定在一个子结构。

之后，作者证明了在这个特殊构造的度量空间和请求序列上,任何确定性在线算法的预期消耗最低也要达到Ω(log²)。

而具体的证明，则采用了数学归纳法。

数学归纳法

数学归纳法虽然名字里有个归纳，实质上却是一种严谨的演绎推理。

它首先验证结论针对序列中的第一项是否成立，然后假设对第k项也成立，接着，只要能证明对第k+1项也成立，结论就可以得到证明。

这个过程就像多米诺骨牌，只要推倒（k+1）一块，其他的牌自然也会随之倒下，这时同时确保第一块有同样的效果，整个体系就完备了。

举个例子，我们知道数列{a(n)=n}的前n项和S(n)=n(n+1)/2，用数学归纳法证明过程如下：

首先n=1时，a(n)=1，S(n)=1(1+1)/2=1，结论成立

然后假设n=k时结论也成立，此时S(k)=k(k+1)/2

那么，当n=k+1时，S(k+1)=S(k)+(k+1)
即S(k+1)=k(k+1)/2+2(k+1)/2
提取公因子(k+1)，这个式子又可以写成(k+2)(K+1)/2
此时n=k+1，n+1=k+2，结论依然成立
所以S(n)=n(n+1)/2得证

任意度量空间消耗下限

而具体到这项研究，作者利用随机性和对称性定义了一个新的序列ρ(w)，并假设在度量空间M(w)中，对随机的ρ(w)，确定性算法的消耗下限为Ω(w²)。

首先对于M(0)，确定性算法的消耗下限为1，此时结论成立。

然后试着将w推广到w+1，构建出M(w+1)的度量空间，它包含两条由多个M(w)组成的对称路径。

在请求ρ(w+1)上，假设此时位于左路径，下一段位于左右路径的概率各为1/2。

如果下阶段位于右路径，算法复杂度将会因为路径切换而升高，不是低消耗。

而如果位于左路径，由于路径上都是一个个M(w)，所以新增部分的消耗下限就是Ω(w²)（此为归纳法假设）。

于是对于w+1段路径，可以将每一段的消耗Ω(w²)累加，即为(w+1)Ω(w²)，结合Ω的定义，最终可以证明M(w+1)的最低消耗为Ω((w+1)²)，进而证明假设成立。

回到最初的度量空间

而作者构建的M(w+1)都是由6个M(w)组成，则M(w)的大小n=|M(w)|=O(6^w)，取对数得log|M(w)|=w·log6。

代入Ω(w²)中，得到在n点度量空间中，消耗下限为Ω((logn/log6)²)，而当n=k时，消耗下限则为Ω((logk/log6)²)。

而log6为一个2到3之间的常数，除以这样一个数不会带来结果的显著改变，也就证明了k-server问题中消耗不低于Ω(log²k)的结论。

当k足够大时，log²k显然大于logk，因此在这样的k-server问题中，实现O(logk)级别的低消耗是不可能的。

而此前人们一直认为可以用这样的消耗解决所有的k-server问题，因此反例的出现便宣告了这一设想的终结。

论文地址：
https://dl.acm.org/doi/pdf/10.1145/3564246.3585132
参考链接：
https://www.quantamagazine.org/researchers-refute-a-widespread-belief-about-online-algorithms-20231120/