کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435910 | 689950 | 2015 | 11 صفحه PDF | دانلود رایگان |
We study a discrete asynchronous dynamical system on hypergraphs that can be regarded as a natural extension of annihilating walks along two directions: first, the interaction topology is a hypergraph; second, the “number of particles” at a vertex of the hypergraph is an element of a finite ring ZpZp of integers modulo an odd number p≥3p≥3. Equivalently particles move on a hypergraph, with a moving particle at a vertex being replaced by one indistinguishable copy at each neighbor in a given hyperedge; particles at a vertex collectively annihilate when their number reaches p.The boolean version of this system arose in earlier work [22] motivated by the statistical physics of social balance [3] and [2], generalizes certain lights-out games [31] to finite fields and also has some applications to the complexity of local search procedures [23].Our result shows that under a liberal sufficient condition on the nature of the interaction hypergraph there exists a polynomial time algorithm (based on linear algebra over ZpZp) for deciding reachability and recurrence of this dynamical system. Interestingly, we provide a counterexample that shows that this connection does not extend to all graphs.
Journal: Theoretical Computer Science - Volume 580, 17 May 2015, Pages 83–93