Skip to Main content Skip to Navigation
Conference papers

On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules

Abstract : We study how hard is to determine some fundamental properties of dynamics of certain types of network automata. We address the computational complexity of determining how many different possible dynamic evolutions can arise from some structurally very simple, deterministic and sparsely connected network automata. In this as well as our prior, related work, we try to push the limits on the underlying simplicity of two structural aspects of such network automata: (i) the uniform sparseness of their topologies, and (ii) severely restricted local behaviors of the individual agents (that is, the local update rules of the network nodes). In this endeavor, we prove that counting the Fixed Point (FP) configurations and the predecessor and ancestor configurations in two classes of network automata, called Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively), are computationally intractable problems. Moreover, this intractability is shown to hold when each node in such a network is required to update according to (i) a monotone Boolean function, (ii) a symmetric Boolean function, or even (iii) a simple threshold function that is both monotone and symmetric. Furthermore, the hardness of the exact enumeration of FPs and other types of configurations of interest remains to hold even in some severely restricted cases with respect to both the network topology and the diversity (or lack thereof) of individual node's local update rules. Namely, we show that the counting problems of interest remain hard even when the nodes of an SDS or SyDS use at most two different update rules from a given restricted class, and, additionally, when the network topologies are constrained so that each node has only $c = O(1)$ neighbors for small values of constant $c$. Our results also have considerable implications for other discrete dynamical system models studied in applied mathematics, physics, biology and computer science, such as Hopfield networks and spin glasses. In particular, one corollary of our results is that determining the memory capacity of sparse discrete Hopfield networks (viewed as associative memories) remains computationally intractable even when the interconnection and dependence structure among the nodes of a Hopfield network is severely restricted.
Complete list of metadata

Cited literature [69 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 2:16:29 PM
Last modification on : Tuesday, March 7, 2017 - 3:06:52 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:02:02 AM


Publisher files allowed on an open archive




Predrag T. Tošić. On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. pp.125-144, ⟨10.46298/dmtcs.2757⟩. ⟨hal-01185493⟩



Record views


Files downloads