• 欢迎光临~

Predecessor Lower Bounds

开发技术 开发技术 2022-06-19 次浏览

1 概述

在字RAW模型中讨论Van Emde Boas树,y-fast树和融合树作为求一个元素的前序和后续的上界:

[O(min{lgomega, lg_omega n}) ]

现在我们讨论前序问题cell-probe复杂性下界,特别的如果这个界是针对静态问题的并且将问题限定在多项式空间,我们在使用round elimination technique技术的communication model中得到下界为:

[Omega(min{frac{lg(omega)}{lglg(n)},lg_omega n}) ]

上述下界表明通过求Van Emde Boas树和融合树的最小值可以得到求元素前序问题的最优的复杂度,可以达到(lglg)级。
上述得到的界是十分优雅的,它们只依赖于信息论(此处有一个问题:是否任何操作都可以做到这一点?)。上述上界都使用了位操作和C风格的操作,由此可以看出他们都依赖于一些计算机技术特性。

2 前人关于前序问题下界的研究

2.1问题描述

给定一个数据结构(由n个(omega)-bits整数组成的集合S)和一个查询操作(查找元素x, 并且x可能不在S中),我们的目标是尽可能快的找到集合S中x的前序元素。我们可以用(O(2^omega))的空间存储预先计算好的所有结果,实现恒定时间的查询。为了避免将问题平凡化,我们假设数据结构用(O(n^(O(1))))的空间。
我们即将讨论的结果实际上是针对一个更容易的问题,即染色前序问题。在此问题中,S的每个元素都被染成红色或蓝色,目标是返回S中x的前序的颜色。由于我们可以用前身问题的解决方案来解决彩色前身问题,这就为我们的原始问题提供了一个更强的下限。

2.2结果

  • Ajtai证明了第一个(omega(1))(即超常数)下界,表明(forallomega)(exists n)可以得到(Omega(sqrtlgomega))查询时间。
  • Miltersen在communication复杂度方面更连贯地重新表述了相同的证明思想。然后展示了两个结果:
    • (forallomega)(exists n)可以得到(Omega(sqrtlgomega))查询时间
    • (forall n)(existsomega)可以得到(Omega(sqrtlg n))查询时间
  • Miltersen, Nisan, Safra, 和Widgerson 介绍了round elimination technique ,并利用它给出了相同下限的简洁证明。
  • Beame和Fich证明了两个强界。
    • (forallomega)(exists n)可以得到(Omega(frac{lgomega}{lglgomega}))查询时间
    • (forall n)(existsomega)可以得到(Omega(sqrtfrac{lg n}{lglg n}))查询时间

他们还给出了一个静态数据结构取得(O(min{frac{lgomega}{lglgomega},sqrtfrac{lg n}{lglg n}})),该方法表明,如果我们坚持使用纯界(仅依赖于n或仅依赖于w的界),上述两个强界是最佳的。

  • Xiao独立地证明了与Beame和Fich相同的两个下界。
  • Sen和Venkatesh给出了一个更强的round elimination定理的版本。它给出了Beame和Fich以及Xiao的相同界的一个更简洁的证明。Fich和Xiao的相同界提供了更简洁的证明。
  • Patrascu和Thorup给出了静态问题中n、w和空间之间的严格权衡。假设空间为(n·2^a) 其中(a=O(lglg n)),他们发现了一个下限为:

[Theta(min{log_omega n, lg(frac{omega - lg n}{a}),frac{lgfrac{omega}{a}}{lg(frac{a}{lg n}lgfrac{w}{a})},frac{lgfrac{omega}{a}}{lg(lgfrac{omega}{a}/lgfrac{lg n}{a})}}) ]

一些直观性理解:
- 第一个项看起来像融合树。
- 第二项约等于是(lg w),相似于Van Emde Boas。
- 最后两个项没有一个好的直观性理解。它们看起来有点类似于Van Emde Boas(lgfrac{omega}{a})但当a很大时,它们会改善一些因素。
如果我们有(O(n polylg n))空间和(a=O(lglg n)),则得到如下结论:
- 如果(w=O(polylg n)),则Van Emde Boas树对小的(omega)来说是最优的。
- 如果(lgomega=Omega(sqrtlg nlglg n)),则融合树对大的(omega)是最优的。
- 在小和大的(omega)之间,界为(Theta(min{log_omega n, frac{lgomega}{lgfrac{lgomega}{lglg n}}}))

3 Communication Complexity

3.1 Communication complexity观点

我们在通信复杂性模型中考虑这个问题。在这个通用模型中,Alice知道一个值(x),Bob知道一个值(y)。他们想共同计算某个函数(f(x, y))。然而,他们被限制在一个协议中,在这个协议中他们交替向对方发送消息。此外,Alice的信息只能是(a)比特长,而Bob的信息只能是(b)比特长。我们可能期望(x)(y)(a)(b)有更多的比特,所以你可能不得不发送多个信息。我们把这个问题看成是一轮一轮的通信,其中一轮是Alice与Bob通信,然后Bob与Alice通信。
将这个模型应用于着色前序问题,我们可以认为Alice是查询算法,她知道查询(x)。Bob内存/RAM,他知道数据结构(y)。 他们一起想找到(f(x, y)),也就是彩色前身查询的答案。直观地说,一轮通信是一次内存读取,Alice想向Bob "询问 "数据结构中的值以便她能计算出答案。
因此,Alice的信息将是地址位,所以(a=O(lg(space)))。鲍勃将返回存储在数据结构中的值,所以(b=w),字的大小。每一 "轮 "通信包括两个消息,对应于cell porbe模型中的一个探针。(这是一个静态问题,所以我们只有cell porbe的读取,而不是写入。)因此,消息的数量等于cell porbe数量的两倍。如果我们能在cell porbe模型中建立一个下限,这将意味着在字RAM模型中也有一个下限。

3.2 前序的下界

定义:通信模型中需要的信息数量(也是区域cell porbe的数量)是(Omega(min{lg_a w, lg_b n}))
推论:这意味着Beame-Fich-Xiao下界为(Omega(min{frac{lgomega}{lglgomega},sqrtfrac{lg n}{lglg n}}))
假设在多项式空间,(a=Theta(lg n))。当(log_aomegastackrel{mathrm{Theta}}{=}log_bn)时下界最大,其中(stackrel{mathrm{Theta}}{=})表示在常数因子内相等。求解我们发现:

[frac{lgomega}{lglg n}stackrel{mathrm{Theta}}{=}frac{lg n}{lgomega}Leftrightarrowlgomegastackrel{mathrm{Theta}}{=}sqrt{lg nlglg n}Leftrightarrowlglgomegastackrel{mathrm{Theta}}{=}lglg n ]

利用上述等价关系,我们重写(Omega(min{lg_aomega, lg_bn})):

[Omega(min{frac{lgomega}{lg a}, frac{lg n}{lgomega}})=Omega(min{frac{lgomega}{lglg n},frac{lg n}{sqrt{lg nlglg n}}})=Omega(min{frac{lgomega}{lglgomega},sqrt{frac{lg n}{lglg n}}}) ]

这种表示方法使我们最容易看到Beame-Fich-Xiao的下界。使用上述计算中的一些中间步骤,我们也可以将该界限改写为:

[Omega(min{frac{lgomega}{lglg n}, log_omega n}) ]

这就是我们在概述中提出的形式。这种表示方法使得我们很容易看到,min函数的第一个参数看起来像Van Emde Boas复杂度(最多相差一个(lglg)系数),而第二个参数看起来像融合树复杂度。

4 Round Elimination

让我们回到抽象的通信模型(不一定与前序问题有关)来讨论Round Elimination。Round Elimination给出了一些条件,在这些条件下,第一轮通信可以被消除。为了做到这一点,我们考虑一个任意的 "(k)-fold "的函数(f)
定义 1:让(f^{(k)})当作(f)的一个变体,其中Alice有(k)个输入(x_1,dots ,x_k),而Bob
有输入:(y,i∈1,dots k,)(x_1,dots, x_{i-1}()注意这与爱丽丝的输入重叠)。我们的目标是是计算(f(x_i, y))
现在假设Alice必须发送第一条信息。注意,她必须发送这个消息,即使她还不知道(i)。直观地说,如果(all k),她不太可能发送任何关于(x_i)的信息,这是她的输入中唯一重要的部分。因此,我们可以把通信协议从第二个信息开始。
引理 2(Round Elimination引理):假设有一个f的协议(f^{(k)})有一个协议,其中Alice先发言,使用(m)个信息,错误概率为(delta)。有协议(f),其中Bob先发言,使用(m-1)条信息,错误概率(delta+O(sqrt{a/k}))
直观的:如果(i)是均匀随机选择的(这是最坏的情况),那么在Alice的第一个信息中,"关于(x_i) "的预期比特数是(1/2^{a/k})。Bob可以随机地猜测这些比特;而猜对所有比特的概率是(1/2^{a/k}),所以失败的概率是(1-2^{-a/k})。因为我们对小的(a/k)感兴趣,串联扩展表明,(1-2^{-a/k}≈a/k)。因此,通过消除Alice的信息,错误概率应该增加大约(a/k)。在现实中,这种直觉并不完全正确我们只能将错误的增加限定为(sqrt{a/k}),取决于应用情况这通常还是可以接受的。

5 前序界证明

证明简述:设(t)为 cell probes的数量,或者等价地,为通信的轮数。我们的目标是应用Round Elimination定理(2t)次来消除所有的信息。在这一点上,必须猜出前序的颜色(假设(n'≥2),如定义5.1中的定义),因此成功的概率最多为(frac{1}{2})
如果我们能将错误概率的增加最多限定为(frac{1}{6}t),那么在每一步中应用(2t)的应用将使错误概率从0增加到最多(frac{1}{3})。然而,这使得成功的概率至少为(frac{2} {3})这是个矛盾的问题。
换句话说,没有一个有(t)个cell probes的算法可以解决这个问题,所以(t)是任何静态随机染色前序数据结构预期性能的下限。

5.1 Eliminating Alice→Bob

Alice的输入有(omega')位(初始化,(omega'=omega))。将输入分成(k=Theta(at^2))等大小的块(x_1,dots,x_k),每块大小为(frac{omega'}{k})位,如果我们能将误差的在每一步增加限制为(O(sqrt{frac{a}{at^2}}=O(frac{1}{t}))),然后调整常数将得到(frac{1}{6}t)
我们构建了一棵(omega')位字符串分支因子为(2^{frac{omega'}{k}})的对应于Alice的可能输入的树,也就是数据结构的元素。然后,这棵树的高度为(k)。在最坏的情况下,我们可以限制(n')(初始化,(n'=n))的元素都在第(i)块中不同。Alice和Bob知道输入的结构,所以Bob知道(i)和所有的公共前缀元素(x_1,dots,x_{i-1})。因此,当Alice的信息被消除后,目标就变成了查询(x_i)中的数据结构的第(i)块,而(w')被简化为(frac{omega'}{k} = Θ(frac{omega'}{at^2}))
这种数据结构的一个类比是Van Emde Boas树,因为vEB二进制搜索的层次是找到最长的前缀匹配,并在搜索过程中减少(w')。利用该定理,错误概率增加了(O(sqrt{frac{a}{at^2}}) = O(frac{1}{t})),这正是我们能够负担得起的每次消除的开销。

5.2 Eliminating Bob→Alice

现在,Alice的信息被消除了,Bob首先发言,所以他不知道查询的值。Bob的输入是(n')整数,每个大小为(w')比特。将这些整数分成(k = Θ(bt^2 ))相等的小块的(frac{n'}{k})整数块。记住,融合树可以在一个大小为(frac{n}{w^{1/5}})的集合中,经过(O(1))个cell probes。这里,我们要证明的是,在一次探测之后,你只能递归到一个大小为(frac{n}{w^{O(1)}})的集合。这给出了相同的误差增加界限,即(O(frac{1}{t}))
为了得到下限,对输入进行约束,使第(i)(x_i)以二进制的前缀(i)开始。Alice的查询从一些随机的(lg k)位开始,这决定了哪个块是感兴趣的。如果Bob先说话首先,他不能知道哪个块是感兴趣的。

利用该定理,消除法将错误概率提高了(O(frac{1}{t}));减少(n')(frac{n'}{k} = Θ(frac{n'}{bt^2}))(w')(w' - lg k = w' - Θ(lg(bt^2))). 只要(w')不会变得太小,(w = Ω(lg(bt^2))),这最后一个项可以忽略不计(例如,它将(w')最多减少2个系数)。

5.3 停止

因此,每一轮的消除都会减少(n')(Θ(frac{n'}{bt^2}))(w')(Θ(frac{w'}{at^2}。此外,通过选择适当的常数最后的概率误差的概率最多为)frac{1}{3}$。

(w'0=O(lg(bt^2)))(n'=2)时,我们停止消除。如果这些停止条件得到满足,我们已经证明了我们的下限:要么最初有很多轮,我们可以做足够的淘汰,把(n)(w)减少到这些小值,或者我们有一个协议,可以用零消息给出答案的答案。但是,这将意味着错误概率最多为$frac{1}{3},这是不可能的。因此,我们必须处于第一种情况(停止条件得到满足)。

因此,我们已经建立了一个下限(t=Ω(min{lg_{at^2}omega, lg_{bt^2}n}))。然而,由于(t=O(lg n))(a ≥ lg n),我们有(a ≤ at^2 ≤ a^3。 同样地,因为)t = O(lg omega),b = omega(,我们有)b ≤ bt^3 ≤ b^3(。 因此,我们可以得出结论:)t = Ω(min{lg_a omega, lg_b n})$。

6 Round Elimination定理的证明简述

6.1 一些信息理论基础知识

定义3: (H(x)),称为(x)的熵,是表示随机变量(x)的分布的平均所需的比特数。

[H(x)=mathop{Sigma} limits_{x_0}Pr[x=x_0]·lgfrac{1}{Pr[x=x_0]} ]

定义4: H(x | y)是给定y的x的条件熵:如果y是已知的,x的熵:

[H(x|y)=E_{y_0}[H(x|y=y_0)] ]

定义5: I(x : y)是x和y之间的相互或共享信息:

[I(x : y) = H(x) + H(y) − H((x, y)) = H(x) − H(x | y) ]

(I(x : y | z))的定义与(H(x | y))相似。

6.2 The Round Elimination Lemma

称Alice的第一个信息为(m = m(x_1, ... , x_k))。接下来,我们利用信息论中的一个巧妙的定理将熵重写为一个总和,这可以被认为是 "信息的连锁规则"。

[a = |m| ≥ H(m) = mathop{Sigma} limits_{i=1}^kI(x_i: m | x_1, . . . , x_{i−1}) ]

如果(i)均匀地分布在({1, . . , k}),那么(E_i[I(x : m | x1, ... , xk)] = frac{H(m)}{k} ≤ frac{a}{k})。 这就是为什么(frac{a}{k})是对Bob能从信息中了解到多少比特关于Alice的信息的估计。注意,我们限定了(I(xi: m | x1, . . , xi-1)),所以即使Bob已经知道(x_1, . . , x_{i-1})并收到了(m),他仍然最多能学到(frac{a}{k})位的信息。

为了证明这条定理,我们必须在假定的(f)的协议下建立一个(f^{(k)})的协议。 我们可以构建一个协议¥f(x, y)¥,如下所示:

  • 固定(x_1, . . . , x_{i-1})(i)是先验的(双方都知道)随机的。
  • Alice假设$ x_i = x$。
  • 运行(f^{(k)})协议,从第二个信息开始,假设第一个信息是(m = m(x_1, . . , x_{i-1}, widehat{x}_i, . . . ,widehat{x}_k)),其中xj是一个从分布中抽取的随机变量。现在,第一个信息并不取决于(x_i = x)(甚至(x_i)是随机选择的),所以Bob可以自己生成它,而不需要从Alice那里得到任何初始信息。
  • 现在Alice有一些真实的(x),她必须用它作为(x_i)而且几乎可以肯定的是,(widehat{x_i} neq x)。我们知道,(I(x_i: m))非常小,所以信息并不真正依赖于(x_i)。这意味着一个随机的信息可能是好的: Alice现在可以固定(x_{i+1}, . . . , x_k),这样对于期望的(x_i = x),(m(x_1, . . . , x_{i-1}, widehat{x}_i, . . . ,widehat{x}_k) = m(x_1, . . , x_{i-1}, x, . . , x_k))

最后一步是关键的一步,它也引入了一个错误概率为(O(sqrt{frac{a}{k}})). 这可以可以根据信息论中的 "平均编码定理 "来证明。还存在一个这个定理所解决的更微妙的问题:不仅必须存在(x_{i+1}, .... , x_k)的存在,使Bob对信息的随机猜测变得有效,而且它们的分布与原始分布接近,所以错误概率(δ)不会增加太多。

程序员灯塔
转载请注明原文链接:Predecessor Lower Bounds
喜欢 (0)