论文标题
比较疑问模型中的下限技术和在树上的反转最小化
Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees
论文作者
论文摘要
给定一棵根树及其叶子的排名，可以通过订购树来实现的叶子的最小反转数是多少？阵列中计数反转问题的这种变化源于数学心理学，并评估了曼恩 - 惠特尼统计数据，用于检测分布之间的差异作为一种特殊情况。 我们在比较 - Query模型中研究问题的复杂性，用于分类和选择等问题。对于许多$ n $叶子的树木，我们建立了接近模型中已知最强的下限，即用于排序$ n $项目的$ \ log_2（n！）$的下限。我们显示： （a）$ \ log_2（（（α（1 -α）n）！） - o（\ log n）$ queries是每当树包含一个子树时包含叶子的分数$α$时。这意味着$ \ log_2的下限（（（\ frac {k} {（k+1）^2} n）！ （b）$ \ log_2（n！） - o（\ log n）如果树是二进制的，则需要$查询。 （c）$ \ log_2（n！） - o（k \ log k）$ QUERIES对于某些类别的$ k $的树木，包括具有$ k $的完美树。 下限是通过在比较Query模型中为通用问题$π$开发两种新型技术来获得的，并将它们应用于树上的反转最小化。这两种技术都可以用对称组的Cayley图来描述，而对称组的相邻换位为生成集。考虑由$π$以下值相同的顶点之间的边缘组成的子图。我们表明，至少必须为$π$的任何决策树的大小： （i）此子图的连接组件的数量，以及 （ii）互补子图的平均程度的阶乘除以$ n $。 查询复杂性的下限，然后遵循基本2对数。
Given a rooted tree and a ranking of its leaves, what is the minimum number of inversions of the leaves that can be attained by ordering the tree? This variation of the problem of counting inversions in arrays originated in mathematical psychology, with the evaluation of the Mann--Whitney statistic for detecting differences between distributions as a special case. We study the complexity of the problem in the comparison-query model, used for problems like sorting and selection. For many types of trees with $n$ leaves, we establish lower bounds close to the strongest known in the model, namely the lower bound of $\log_2(n!)$ for sorting $n$ items. We show: (a) $\log_2((α(1-α)n)!) - O(\log n)$ queries are needed whenever the tree has a subtree that contains a fraction $α$ of the leaves. This implies a lower bound of $\log_2((\frac{k}{(k+1)^2}n)!) - O(\log n)$ for trees of degree $k$. (b) $\log_2(n!) - O(\log n)$ queries are needed in case the tree is binary. (c) $\log_2(n!) - O(k \log k)$ queries are needed for certain classes of trees of degree $k$, including perfect trees with even $k$. The lower bounds are obtained by developing two novel techniques for a generic problem $Π$ in the comparison-query model and applying them to inversion minimization on trees. Both techniques can be described in terms of the Cayley graph of the symmetric group with adjacent-rank transpositions as the generating set. Consider the subgraph consisting of the edges between vertices with the same value under $Π$. We show that the size of any decision tree for $Π$ must be at least: (i) the number of connected components of this subgraph, and (ii) the factorial of the average degree of the complementary subgraph, divided by $n$. Lower bounds on query complexity then follow by taking the base-2 logarithm.
