[New England
      Complex Systems Institute]
[Home] [Research] [Education] [Current Section: Activities & Events] [Community] [News] [The Complex World] [About Complex Systems] [About NECSI]
International Conference on Complex Systems (ICCS2006)

Computational Complexity of Counting in Sparsely Networked Discrete Dynamical Systems

Predrag Tosic
Department of Computer Science & National Center for Sup

     Full text: PDF
     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).

Conference Home   |   Conference Topics   |   Application to Attend
Submit Abstract/Paper   |   Accommodation and Travel   |   Information for Participants

Maintained by NECSI Webmaster    Copyright © 2000-2005 New England Complex Systems Institute. All rights reserved.