ECCC-Report TR05-051https://eccc.weizmann.ac.il/report/2005/051Comments and Revisions published for TR05-051en-usThu, 25 Aug 2005 00:00:00 +0300
Revision 2
| ``On Complexity of Counting Fixed Point Configurations in Certain Classes of Graph Automata '' |
Predrag Tosic
https://eccc.weizmann.ac.il/report/2005/051#revision2We 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 the problems of counting the garden of Eden configurations (GEs), as well as all transient configurations, are just as hard in that 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 nodehas a neighborhood size bounded by a small constant.
Thu, 25 Aug 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/051#revision2
Revision 1
| On Complexity of Counting Fixed Point Configurations in Certain Classes of Graph Automata |
Predrag T. Tosic
https://eccc.weizmann.ac.il/report/2005/051#revision1We 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.
Tue, 10 May 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/051#revision1
Paper TR05-051
| On Complexity of Counting Fixed Points in Certain Classes of Graph Automata |
Predrag Tosic
https://eccc.weizmann.ac.il/report/2005/051We 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.
Tue, 26 Apr 2005 09:06:59 +0300https://eccc.weizmann.ac.il/report/2005/051