ECCC-Report TR05-091https://eccc.weizmann.ac.il/report/2005/091Comments and Revisions published for TR05-091en-usWed, 24 Aug 2005 00:00:00 +0300
Revision 1
| ``Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs'' |
Predrag Tosic
https://eccc.weizmann.ac.il/report/2005/091#revision1We study counting various types of configurations in certain classes of graph automata viewed as discrete dynamical systems. The graph automata models of our interest are Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively). These models have been proposed as a mathematical foundation for a theory of large-scale simulations of complex multi-agent systems. Our emphasis in this paper is on the computational complexity of counting the fixed point and the garden of Eden configurations in Boolean SDSs and SyDSs. We have shown in [47] that counting fixed points is, in general, computationally intractable. We show in the present report that this intractability still holds when both the underlying graphs and the node update rules of these SDSs and SyDSs are severely restricted. In particular, we prove that the problems of exactly counting fixed points, gardens of Eden and two other types of S(y)DS configurations are all #P-complete, even if the SDSs and SyDSs are defined over planar bipartite graphs, and each of their nodes updates its state according to a monotone update rule given as a Boolean formula. We thus add these formal discrete dynamical systems to the list of those problem domains for which counting the combinatorial structures of interest is intractable even when the related decision problems are known to be efficiently solvable.
Wed, 24 Aug 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/091#revision1
Paper TR05-091
| Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs |
Predrag Tosic
https://eccc.weizmann.ac.il/report/2005/091We study counting various types of congurations in certain classes of graph
automata viewed as discrete dynamical systems. The graph automata models
of our interest are Sequential and Synchronous Dynamical Systems (SDSs and
SyDSs, respectively). These models have been proposed as a mathematical foun-
dation for a theory of large-scale simulations of complex multi-agent systems.
Our emphasis in this paper is on the computational complexity of counting the
xed point and the garden of Eden congurations in Boolean SDSs and SyDSs.
We have shown in [47] that counting xed points is, in general, computation-
ally intractable. We show in the present report that this intractability still holds
when both the underlying graphs and the node update rules of these SDSs and
SyDSs are severely restricted. In particular, we prove that the problems of exactly
counting xed points, gardens of Eden and two other types of S(y)DS congura-
tions are all #P-complete, even if the SDSs and SyDSs are dened over planar
bipartite graphs, and each of their nodes updates its state according to a mono-
tone update rule given as a Boolean formula. We thus add these formal discrete
dynamical systems to the list of those problem domains for which counting the
combinatorial structures of interest is intractable even when the related decision
problems are known to be enumerationciently solvable.
Tue, 23 Aug 2005 20:41:27 +0300https://eccc.weizmann.ac.il/report/2005/091