On computational complexity of counting fixed points in symmetric boolean graph automata
By
We study computational complexity of counting the fixed point configurations (FPs) in certain classes of graph automata viewed as discrete dynamical systems. We prove that both exact and approximate counting of FPs in Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively) are computationally intractable, even when each node is required to update according to a symmetric Boolean function. We also show that the problems of counting exactly the garden of Eden configurations (GEs), as well as all transient configurations, are in general intractable, as well. Moreover, exactly enumerating FPs or GEs remains hard even in some severely restricted cases, such as when the nodes of an SDS or SyDS use only two different symmetric Boolean update rules, and every node has a neighborhood size bounded by a small constant.
Keywords Cellular and graph automata - sequential and synchronous dynamical systems - configuration space properties - computational complexity - #P-completeness
BibTeX
@inproceedings{conf/uc/TosicA05,
author = "Tosic, Predrag T. and Agha, Gul A.",
editor = "Calude, Cristian and Dinneen, Michael J. and Paun,
Gheorghe and Pérez-Jiménez, Mario J. and Rozenberg, Grzegorz",
title = "On Computational Complexity of Counting Fixed Points in
Symmetric Boolean Graph Automata",
booktitle = "UC",
crossref = "conf/uc/2005",
ee = "http://dx.doi.org/10.1007/11560319_18",
keywords = "complex systems",
pages = "191-205",
year = "2005",
}
@proceedings{conf/uc/2005,
editor = "Calude, Cristian and Dinneen, Michael J. and Paun,
Gheorghe and Pérez-Jiménez, Mario J. and Rozenberg, Grzegorz",
title = "Unconventional Computation, 4th International Conference,
UC 2005, Sevilla, Spain, October 3-7, 2005, Proceedings",
isbn = "3-540-29100-8",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
volume = "3699",
year = "2005",
}