On Complexity of Counting Fixed Points in Certain Classes of Graph Automata

@techreport{citeulike:1723791, abstract = {We study the computational complexity of counting the fixed point configurations in certain discrete dynamical systems. We prove that both exact and approximate counting in Sequential and Synchronous Dynamical Systems (SDSs and SyDS, respectrively) is computationally intractable, even when each node is required to update according to a symmetric Boolean function. We also show that the exact counting of Garden of Eden configurations, as well as of all transient configurations, is just as hard in this setting. Moreover, the hardness of counting holds even in the severely restricted cases, such as when the nodes of a symmetric SDS or SyDS use only two different update rules, and when each node has a neighborhood size bounded by a small constant.}, author = {Tosic, Predrag T. }, citeulike-article-id = {1723791}, journal = {Electronic Colloquium on Computational Complexity}, keywords = {automata, complexity, graph}, organization = {ECCC}, posted-at = {2007-10-03 12:45:04}, priority = {2}, title = {On Complexity of Counting Fixed Points in Certain Classes of Graph Automata}, year = {2005} }

TY - RPRT ID - citeulike:1723791 L3 - citeulike-article-id:1723791 TI - On Complexity of Counting Fixed Points in Certain Classes of Graph Automata JF - Electronic Colloquium on Computational Complexity OR - ECCC N2 - We study the computational complexity of counting the fixed point configurations in certain discrete dynamical systems. We prove that both exact and approximate counting in Sequential and Synchronous Dynamical Systems (SDSs and SyDS, respectrively) is computationally intractable, even when each node is required to update according to a symmetric Boolean function. We also show that the exact counting of Garden of Eden configurations, as well as of all transient configurations, is just as hard in this setting. Moreover, the hardness of counting holds even in the severely restricted cases, such as when the nodes of a symmetric SDS or SyDS use only two different update rules, and when each node has a neighborhood size bounded by a small constant. KW - automata KW - complexity KW - graph AU - Tosic, Predrag PY - 2005/// ER -