All Symmetric Predicates in NSPACE{n~2) Are Stably Computable by the Mediated Population Protocol Model

摘要

This work focuses on the computational power of the Mediated Population Protocol model on complete communication graphs and initially identical edges (SMPP). In particular, we investigate the class MPS of all predicates that are stably computable by the SMPP model. It is already known that MPS is in the symmetric subclass of NSPACE(n2). Here we prove that this inclusion holds with equality, thus, providing the following exact characterization for MPS: A predicate is in MPS iff it is symmetric and is in NSPACE{n~2).