论文标题
在树上分布的本地可检查问题的复杂性格局
The Complexity Landscape of Distributed Locally Checkable Problems on Trees
论文作者
论文摘要
最近的研究表明，在分布式计算的本地模型中，本地可检查标签问题（LCL）问题的复杂性格局存在差距。例如，有限度图上任何LCL问题的确定性圆形复杂性要么是$ O（\ log^\ ast n）$或$ω（\ log n）$ [Chang，Kopelowitz和Pettie，Focs 2016]。现在，LCL问题的复杂性格局已经得到了很好的理解，但是一些问题仍然开放。 对于有限度的树，对于每个正整数$ k $ [Chang and Pettie，focs 2017]，圆形复杂性$θ（n^{1/k}）$存在LCL问题。猜想没有LCL问题具有圆形复杂性$ O（N^{1/（K-1）}）$和$ω（n^{1/k}）$上的$ω（n^{1/k}）$。截至目前，仅证明了$ k = 2 $的情况[Balliu等，Disc 2018]。 在本文中，我们表明，对于有限度树的LCL问题，确实存在$θ（n^{1/（k-1）}）$和$θ（n^{1/k}）$之间的差距。我们的证明是建设性的，因为它提供了一种顺序算法，该算法决定给定LCL问题所属的差距的哪一侧。我们还表明，区分$θ（1）$ - 圆形和$θ（n）$ - 圆形LCL问题是有限的。这可以改善先前的pspace-hardness结果[Balliu等，PODC 2019]。
Recent research revealed the existence of gaps in the complexity landscape of locally checkable labeling (LCL) problems in the LOCAL model of distributed computing. For example, the deterministic round complexity of any LCL problem on bounded-degree graphs is either $O(\log^\ast n)$ or $Ω(\log n)$ [Chang, Kopelowitz, and Pettie, FOCS 2016]. The complexity landscape of LCL problems is now quite well-understood, but a few questions remain open. For bounded-degree trees, there is an LCL problem with round complexity $Θ(n^{1/k})$ for each positive integer $k$ [Chang and Pettie, FOCS 2017]. It is conjectured that no LCL problem has round complexity $o(n^{1/(k-1)})$ and $ω(n^{1/k})$ on bounded-degree trees. As of now, only the case of $k = 2$ has been proved [Balliu et al., DISC 2018]. In this paper, we show that for LCL problems on bounded-degree trees, there is indeed a gap between $Θ(n^{1/(k-1)})$ and $Θ(n^{1/k})$ for each $k \geq 2$. Our proof is constructive in the sense that it offers a sequential algorithm that decides which side of the gap a given LCL problem belongs to. We also show that it is EXPTIME-hard to distinguish between $Θ(1)$-round and $Θ(n)$-round LCL problems on bounded-degree trees. This improves upon a previous PSPACE-hardness result [Balliu et al., PODC 2019].
