**Abstract:** We study computational complexity of counting the fixed point configurations (FPs), garden of Eden configurations (GEs), and predecessor configurations in certain types of graph 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 hold even 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. We also show that the problems of counting exactly the garden of Eden configurations (GEs), all transient configurations, and all predecessors of an arbitrary configuration, are also computationally intractable. Moreover, the hardness of the exact enumeration of FPs and other types of configurations holds even in some severely restricted cases, i.e., when the nodes of an SDS or SyDS use at most two different Boolean functions from an appropriately restricted class of the node update rules, and, additionally, when the underlying graphs are constrained so that each node has only c = O(1) neighbors for small values of c.