Computational Complexity of Counting in Sparsely Networked Discrete Dynamical Systems
Department of Computer Science & National Center for Sup
Last modified: August 9, 2006
Predrag Tosic, Department of Computer Science, UIUC:
``Computational Complexity of Counting in Sparsely Networked Discrete Dynamical Systems"
We study the computational complexity of counting various types of configurations in certain classes of network automata viewed as discrete dynamical systems. Examples of types of configurations of interest are the stable or fixed point configurations (FPs), the unreachable or garden of Eden configurations (GEs), and the predecessor configurations. We show in this paper that counting the fixed points of Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively) is, in general, computationally intractable. This intractability is shown to still hold when each node of an SDS or SyDS is required to update according to either (i) a monotone linear threshold Boolean function, or (ii) a symmetric Boolean function. Furthermore, the hardness of the exact enumeration of FPs holds even in some severely restricted cases. Concretely, counting FPs of symmetric (alternatively, monotone) Boolean SDSs and SyDSs is hard even when the nodes of an SDS or SyDS use at most two different symmetric (monotone) Boolean functions, and, additionally, when the underlying graphs are constrained so that each node has only c = O(1) neighbors for small values of c. Our results have considerable implications for a number of domains, from the loosely coupled multi-agent systems in distributed AI, to connectionist AI (Hopfield networks), statistical physics (the Ising model and spin glasses), and theoretical biology (Kauffman’s random Boolean networks).