Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-159 | 3rd October 2006 00:00

Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata



We study the computational complexity of counting the fixed point configurations (FPs), the predecessor configurations and the ancestor configurations in certain classes of graph or network automata viewed as discrete dynamical systems. Early results of this investigation are presented in two recent ECCC reports [39, 40]. In particular, it is proven in [40] that both exact and approximate counting of FPs in the two closely related classes of Boolean network automata, called Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively), are computationally intractable problems when each node is required to update according to a monotone Boolean function. In the present paper, we further strengthen those results by showing that the intractability of exact enumeration of FPs and several other types of configurations of a monotone Boolean SDS or SyDS still holds even when (i) the monotone update rules are restricted to linear threshold functions, and (ii) the underlying graph is uniformly sparse. By the uniform sparseness we mean that every node in the graph has its degree bounded by c = O(1)for a small value of constant. In particular, we prove that exactly enumerating FPs in such SDSs and SyDSs remains #P-complete even when no node degree exceeds 3. Among other consequences, we show that this result also implies intractability of determining the exact memory capacity of discrete Hopfield networks with uniformly sparse and nonnegative integer weight matrices.

ISSN 1433-8092 | Imprint