Lindley Hall 102 (4:45pm-5:15pm)

Predrag Tosic
University of Illinois at Urbana-Champaign

Computational Complexity of Some Enumeration Problems in Sparse Boolean Network Automata

We study computational complexity of counting the fixed point configurations (FPs) in certain types of network automata. We prove that both exact and approximate counting of fixed points in Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively) are computationally intractable problems. This intractability is shown to still hold when each node 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. Moreover, the hardness of the exact enumeration of FPs holds even in some severely restricted cases, namely, when the nodes of an SDS or SyDS use at most two different update rules from a given class, and, additionally, when the underlying graphs are constrained so that each node has only c = O(1) neighbors for small values of c. One corollary of these results is that determining the exact memory capacity of sparse discrete Hopfield networks (viewed as associative memories) is also computationally intractable.