






















Population protocols are a model of computation in which indistinguishable mobile agents interact in pairs to decide a property of their initial configuration. Originally introduced by Angluin et. al. in 2004 with a constant number of states, research nowadays focuses on protocols where the space usage depends on the number of agents. The expressive power of population protocols has so far however only been determined for protocols using $o(\log n)$ states, which compute only semilinear predicates, and for $Ω(n)$ states. This leaves a significant gap, particularly concerning protocols with $Θ(\log n)$ or $Θ(\mathsf{polylog}~ n)$ states, which are the most common constructions in the literature. In this paper we close the gap and prove that for any $ε > 0$ and $f {\in}Ω(\log n) {\cap}O(n^{1-ε})$, both uniform and non-uniform population protocols with $Θ(f(n))$ states can decide exactly those predicates, whose unary encoding lies in $\mathsf{NSPACE}(f(n) \log n)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。