Dichotomy results for fixed point counting in Boolean dynamical systems. (English) Zbl 1318.68089
Summary: We present dichotomy theorems regarding the computational complexity of counting fixed points in Boolean (discrete) dynamical systems, i.e., finite discrete dynamical systems over the domain \(\{0, 1 \}\). For a class \(\mathcal{F}\) of Boolean functions and a class \(\mathcal{G}\) of graphs, an \((\mathcal{F}, \mathcal{G})\)-system is a Boolean dynamical system with local transitions functions lying in \(\mathcal{F}\) and graphs in \(\mathcal{G}\). We show that, if local transition functions are given by lookup tables, then the following complexity classification holds: Let \(\mathcal{F}\) be a class of Boolean functions closed under superposition and let \(\mathcal{G}\) be a graph class closed under taking minors. If \(\mathcal{F}\) contains all min-functions, all max-functions, or all self-dual and monotone functions, and \(\mathcal{G}\) contains all planar graphs, then it is \(\# \mathrm P\)-complete to compute the number of fixed points in an \((\mathcal{F}, \mathcal{G})\)-system; otherwise it is computable in polynomial time. We also prove a dichotomy theorem for the case that local transition functions are given by formulas (over logical bases). This theorem has a significantly more complicated structure than the theorem for lookup tables. A corresponding theorem for Boolean circuits coincides with the theorem for formulas.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C83 | Graph minors |
| 37B15 | Dynamical aspects of cellular automata |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68Q80 | Cellular automata (computational aspects) |
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
References:
| [1] | Bar-Yam, Y., Dynamics of Complex Systems. Studies in Nonlinearity (2003), Addison-Wesley Publishing Co.: Addison-Wesley Publishing Co. Reading, MA |
| [2] | Barrett, C. L.; Hunt, H. B.; Marathe, M. V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E., Predecessor and permutation existence problems for sequential dynamical systems, (Proceedings of the Conference on Discrete Models for Complex Systems. Proceedings of the Conference on Discrete Models for Complex Systems, DMCS’03. Proceedings of the Conference on Discrete Models for Complex Systems. Proceedings of the Conference on Discrete Models for Complex Systems, DMCS’03, Discrete Mathematics and Theoretical Computer Science Proceedings, vol. AB (2003)), 69-80 · Zbl 1073.68684 |
| [3] | Barrett, C. L.; Hunt, H. B.; Marathe, M. V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E., Reachability problems for sequential dynamical systems with threshold functions, Theoret. Comput. Sci., 295, 1-3, 41-64 (2003) · Zbl 1045.68062 |
| [4] | Barrett, C. L.; Hunt, H. B.; Marathe, M. V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E., Complexity of reachability problems for finite discrete dynamical systems, J. Comput. System Sci., 72, 7, 1317-1345 (2006) · Zbl 1119.68095 |
| [5] | Barrett, C. L.; Hunt, H. B.; Marathe, M. V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E.; Tošić, P. T., Gardens of Eden and fixed points in sequential dynamical systems, (Proceedings of the 1st International Conference on Discrete Models: Combinatorics, Computation and Geometry. Proceedings of the 1st International Conference on Discrete Models: Combinatorics, Computation and Geometry, DM-CCG’01. Proceedings of the 1st International Conference on Discrete Models: Combinatorics, Computation and Geometry. Proceedings of the 1st International Conference on Discrete Models: Combinatorics, Computation and Geometry, DM-CCG’01, Discrete Mathematics and Theoretical Computer Science Proceedings, vol. AB (2001)), 241-259 · Zbl 1017.68055 |
| [6] | Barrett, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation II: sequential dynamical systems, Appl. Math. Comput., 107, 2-3, 121-136 (2000) · Zbl 1049.68149 |
| [7] | Barrett, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation III: equivalence of SDS, Appl. Math. Comput., 122, 3, 325-340 (2001) · Zbl 1050.68161 |
| [8] | Barrett, C. L.; Reidys, C. M., Elements of a theory of computer simulation I: sequential CA over random graphs, Appl. Math. Comput., 98, 2-3, 241-259 (1999) · Zbl 0927.68114 |
| [9] | Böhler, E.; Creignou, N.; Reith, S.; Vollmer, H., Playing with Boolean blocks, part I: Post’s lattice with applications to complexity theory, ACM SIGACT News, 34, 4, 38-52 (2003) |
| [10] | Buss, S. R.; Papadimitriou, C. H.; Tsitsiklis, J. N., On the predictability of coupled automata: an allegory about chaos, Complex Systems, 5, 525-539 (1991) · Zbl 0760.68031 |
| [11] | Cattell, K.; Dinneen, M. J., A characterization of graphs with vertex cover up to five, (Proceeding of the International Workshop on Orders, Algorithms, and Applications. Proceeding of the International Workshop on Orders, Algorithms, and Applications, ORDAL’94. Proceeding of the International Workshop on Orders, Algorithms, and Applications. Proceeding of the International Workshop on Orders, Algorithms, and Applications, ORDAL’94, Lecture Notes in Computer Science, vol. 831 (1994), Springer-Verlag: Springer-Verlag Berlin), 86-99 · Zbl 0953.05505 |
| [12] | Creignou, N.; Hermann, M., Complexity of generalized satisfiability counting problems, Inform. and Comput., 125, 1, 1-12 (1996) · Zbl 0853.68110 |
| [13] | Diestel, R., Graph Theory, Graduate Texts in Mathematics (2003), Springer-Verlag: Springer-Verlag Berlin |
| [14] | Flum, J.; Grohe, M., The parameterized complexity of counting problems, SIAM J. Comput., 33, 4, 892-922 (2004) · Zbl 1105.68042 |
| [15] | Green, F., NP-complete problems in cellular automata, Complex Systems, 1, 3, 453-474 (1987) · Zbl 0648.68067 |
| [16] | Hemaspaandra, L. A.; Ogihara, M., The Complexity Theory Companion, Texts in Theoretical Computer Science. An EATCS Series (2002), Springer-Verlag: Springer-Verlag Berlin · Zbl 0993.68042 |
| [17] | Hopfield, J. J., Neural networks and physical systems with emergent collective computational abilities, Proc. Natl. Acad. Sci. USA, 79, 8, 2554-2558 (1982) · Zbl 1369.92007 |
| [18] | Kosub, S., Dichotomy results for fixed-point existence problems for boolean dynamical systems, Special Issue on Modeling and Analysis of Complex Systems. Special Issue on Modeling and Analysis of Complex Systems, Math. Comput. Sci., 1, 3, 487-505 (2008) · Zbl 1138.68034 |
| [19] | Kosub, S.; Homan, C. M., Dichotomy results for fixed point counting in boolean dynamical systems, (Proceedings of the 10th Italian Conference on Theoretical Computer Science. Proceedings of the 10th Italian Conference on Theoretical Computer Science, ICTCS’07 (2007), World Scientific: World Scientific Singapore), 163-174 |
| [20] | Linial, N., Hard enumeration problems in geometry and combinatorics, SIAM J. Algebr. Discrete Methods, 7, 2, 331-335 (1986) · Zbl 0596.68041 |
| [21] | Milner, R., Communicating and Mobile Systems: The \(π\)-Calculus (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0942.68002 |
| [22] | Post, E. L., The Two-Valued Iterative Systems of Mathematical Logic, Annals of Mathematics Studies, vol. 5, 1-122 (1941) · Zbl 0063.06326 |
| [23] | Provan, J. S.; Ball, M. O., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput., 12, 4, 777-788 (1983) · Zbl 0524.68041 |
| [24] | Rabinovich, A. M., Complexity of equivalence problems for concurrent systems of finite agents, Inform. and Comput., 139, 2, 111-129 (1997) · Zbl 0892.68061 |
| [25] | Robertson, N.; Seymour, P. D., Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B, 41, 1, 92-114 (1986) · Zbl 0598.05055 |
| [26] | Robertson, N.; Seymour, P. D., Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B, 92, 2, 325-357 (2004) · Zbl 1061.05088 |
| [27] | Sutner, K., On the computational complexity of finite cellular automata, J. Comput. System Sci., 50, 1, 87-97 (1995) · Zbl 0827.68078 |
| [28] | Tošić, P. T., On complexity of counting fixed point configurations in certain classes of graph automata, Electron. Colloq. Comput. Complex., 12, 51 (2005) |
| [29] | Tošić, P. T., On the complexity of counting fixed points and gardens of Eden in sequential dynamical systems on planar bipartite graphs, Internat. J. Found. Comput. Sci., 17, 5, 1179-1203 (2006) · Zbl 1100.68072 |
| [30] | Tošić, P. T.; Agha, G. A., On computational complexity of counting fixed points in symmetric boolean graph automata, (Proceedings of the 4th International Conference on Unconventional Computation. Proceedings of the 4th International Conference on Unconventional Computation, UC’05. Proceedings of the 4th International Conference on Unconventional Computation. Proceedings of the 4th International Conference on Unconventional Computation, UC’05, Lecture Notes in Computer Science, vol. 3699 (2005), Springer-Verlag: Springer-Verlag Berlin), 191-205 · Zbl 1161.68608 |
| [31] | Vadhan, S. P., The complexity of counting in sparse, regular, and planar graphs, SIAM J. Comput., 31, 2, 398-427 (2002) · Zbl 0994.68070 |
| [32] | Valiant, L. G., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 3, 410-421 (1979) · Zbl 0419.68082 |
| [33] | von Neumann, J., Theory of Self-Reproducing Automata (1966), University of Illinois Press: University of Illinois Press Champaign, IL, Arthur W. Burks (Ed.) |
| [34] | Wolfram, S., Cellular Automata and Complexity. Collected Papers (1994), Addison-Wesley Publishing Co.: Addison-Wesley Publishing Co. Reading, MA · Zbl 0823.68003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
