On complexity of counting fixed point configurations in certain classes of graph automata

We study computational complexity of counting the fixed point configurations (FPs) in certain discrete dynamical systems. We prove that counting FPs in Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively) is computationally intractable, even when each node is required to update according to a symmetric Boolean function. We also show that counting the garden of Eden configurations (GEs), as well as all transient configurations, is just as hard in this setting. Moreover, the hardness of enumerating FPs holds 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 when each node has a neighborhood size bounded by a small constant