Autori: Gabriel Istrate

Editorial: Theoretical Computer Science , 580, p.83-93, 2015.

Rezumat:

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 Z_p of integers modulo an odd number p>= 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 motivated by our earlier work on the statistical physics of social balance, generalizes certain lights-out games to finite fields and also has some applications to the complexity of local search procedures.

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 Z_p) 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.

For a preprint version see http://tcs.ieat.ro/wp-content/uploads/2013/06/arxiv.pdf

Cuvinte cheie: discrete complex systems, ights-out games, reachability

URL: http://www.sciencedirect.com/science/article/pii/S0304397515001711