Predecessor existence problems for finite discrete dynamical systems. (English) Zbl 1137.68410
Theor. Comput. Sci. 386, No. 1-2, 3-37 (2007); errata ibid. 395, No. 1, 132-133 (2008).
Summary: We study the predecessor existence problem for finite discrete dynamical systems. Given a finite discrete dynamical system \(\mathcal S\) and a configuration \(\mathcal C\), the Predecessor existence (or Pre) problem is to determine whether there is a configuration \(\mathcal C^{\prime}\) such that \(\mathcal S\) has a transition from \(\mathcal C^{\prime}\) to \(\mathcal C\). In addition to the decision version, we also study the following variants: the #-Predecessor existence (or #Pre) problem – counting the number of predecessors, the Unique-Predecessor existence (or UPre) problem – deciding whether there is a unique predecessor, and the Ambiguous-Predecessor existence (or APre) problem – given a configuration \(\mathcal C\) and a predecessor \(\mathcal C^{\prime}\) of \(\mathcal C\), deciding whether there is a different predecessor \(\mathcal C^{\prime\prime}\) of \(\mathcal C\).
General techniques are presented for simultaneously characterizing the computational complexity of the Pre problem and its three variants. Our hardness results are based on the concept of simultaneous reductions: single transformations that can be used to simultaneously prove the hardness of the different variants of the Pre problem for their respective complexity classes. Our easiness results are based on dynamic programming and they extend the previous results on Pre problem for one-dimensional cellular automata. The hardness results together with the easiness results provide a tight separation between easy and hard instances. Further, the results imply similar bounds for other classes of finite discrete dynamical systems including discrete Hopfield and recurrent neural networks, concurrent state machines, systolic networks and one- and two-dimensional cellular automata. Our results extend the earlier results of Green, Sutner and Orponen on the complexity of the predecessor existence problem and its variants.
General techniques are presented for simultaneously characterizing the computational complexity of the Pre problem and its three variants. Our hardness results are based on the concept of simultaneous reductions: single transformations that can be used to simultaneously prove the hardness of the different variants of the Pre problem for their respective complexity classes. Our easiness results are based on dynamic programming and they extend the previous results on Pre problem for one-dimensional cellular automata. The hardness results together with the easiness results provide a tight separation between easy and hard instances. Further, the results imply similar bounds for other classes of finite discrete dynamical systems including discrete Hopfield and recurrent neural networks, concurrent state machines, systolic networks and one- and two-dimensional cellular automata. Our results extend the earlier results of Green, Sutner and Orponen on the complexity of the predecessor existence problem and its variants.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 37B15 | Dynamical aspects of cellular automata |
| 68Q60 | Specification and verification (program logics, model checking, etc.) |
| 68Q80 | Cellular automata (computational aspects) |
Keywords:
discrete dynamical systems; cellular automata; predecessor existence; data flow analysis; software and hardware verification; computational complexityReferences:
| [1] | Albert, R.; Barabasi, A., Statistical mechanics of complex networks, Reviews of Modern Physics, 74, 1, 47-97 (2002) · Zbl 1205.82086 |
| [2] | Albert, J.; Culik, K., Simple universal cellular automata and its one-way and totalistic version, Complex Systems, 1, 1-16 (1987) · Zbl 0655.68065 |
| [3] | R. Axtell, Why agents? On the Varied Motivations for Agent Computing in the Social Sciences, Center on Social and Economic Dynamics, Working Paper No. 17, Nov. 2000; R. Axtell, Why agents? On the Varied Motivations for Agent Computing in the Social Sciences, Center on Social and Economic Dynamics, Working Paper No. 17, Nov. 2000 |
| [4] | Axtell, R., Effects of interaction topology and activation regime in several multi-agent systems, (Multi Agent Based Simulation. Multi Agent Based Simulation, Lecture Notes in Artificial Intelligence, vol. 1979 (2000), Springer-Verlag: Springer-Verlag New York, NY) |
| [5] | C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, P. Tosic, Gardens of Eden and fixed points in sequential dynamical systems, in: Proc. of the International Conference on Discrete Models — Combinatorics, Computation and Geometry, DM-CCG, Paris, July 2001, pp. 95-110; C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, P. Tosic, Gardens of Eden and fixed points in sequential dynamical systems, in: Proc. of the International Conference on Discrete Models — Combinatorics, Computation and Geometry, DM-CCG, Paris, July 2001, pp. 95-110 · Zbl 1017.68055 |
| [6] | Barrett, C.; Hunt, H.; Marathe, M.; Ravi, S.; Rosenkrantz, D.; Stearns, R., Reachability problems for sequential dynamical systems with threshold functions, Theoretical Computer Science, 295, 1-3, 41-64 (2003) · Zbl 1045.68062 |
| [7] | C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, Predecessor and permutation existence problems for sequential dynamical systems, in: Proceedings of the International Conference on Discrete Models for Complex Systems, DM-CS 2003, Lyon, France, June 2003, pp. 69-80; C. Barrett, H. Hunt III, M. Marathe, S. Ravi, D. Rosenkrantz, R. Stearns, Predecessor and permutation existence problems for sequential dynamical systems, in: Proceedings of the International Conference on Discrete Models for Complex Systems, DM-CS 2003, Lyon, France, June 2003, pp. 69-80 · Zbl 1073.68684 |
| [8] | Barrett, C.; Mortveit, H.; Reidys, C., Elements of a theory of computer simulation III: equivalence of SDSs, Applied Mathematics and Computation, 122, 3, 325-340 (2001) · Zbl 1050.68161 |
| [9] | H. Bodlaender, Treewidth: Algorithmic techniques and results, in: Proc. 22nd Symposium on Mathematical Foundations of Computer Science, MFCS 1997, Bratislava, Slovak Republic, August 1997, pp. 29-36; H. Bodlaender, Treewidth: Algorithmic techniques and results, in: Proc. 22nd Symposium on Mathematical Foundations of Computer Science, MFCS 1997, Bratislava, Slovak Republic, August 1997, pp. 29-36 · Zbl 0941.05057 |
| [10] | Creignou, N.; Hermann, M., Complexity of generalized satisfiability counting problems, Information and Computation, 125, 1, 1-12 (1996) · Zbl 0853.68110 |
| [11] | Cheng, S.; Kramer, J., Tractable dataflow analysis for distributed systems, IEEE Transactions on Software Engineering, 20, 8, 579-593 (1994) |
| [12] | Creignou, N.; Khanna, S.; Sudan, M., (Complexity Classifications of Boolean Constraint Satisfaction Problems. Complexity Classifications of Boolean Constraint Satisfaction Problems, SIAM Monographs on Discrete Mathematics and Applications, vol. 7 (2001), SIAM: SIAM Philadelphia, PA) · Zbl 0981.68058 |
| [13] | Culik, K.; Pachl, J.; Yu, S., On the limit sets of cellular automata, SIAM Journal on Computing, 18, 4, 831-842 (1989) · Zbl 0691.68060 |
| [14] | Culik, K.; Karhumäki, J., On totalistic systolic networks, Information Processing Letters, 26, 5, 231-236 (1988) · Zbl 0654.68058 |
| [15] | M. D’Antonio, G. Delzanno, SAT-based analysis of cellular automata, in: Proc. Italian Symp. Computational Logic, Parma, Italy, June 2004, pp. 745-754; M. D’Antonio, G. Delzanno, SAT-based analysis of cellular automata, in: Proc. Italian Symp. Computational Logic, Parma, Italy, June 2004, pp. 745-754 · Zbl 1116.68508 |
| [16] | A. DeHon, Very large scale spatial computing, in: Proc. Third Intl. Conf. Unconventional Models of Computation, UMC’02, Kobe, Japan, October 2002, pp. 27-37; A. DeHon, Very large scale spatial computing, in: Proc. Third Intl. Conf. Unconventional Models of Computation, UMC’02, Kobe, Japan, October 2002, pp. 27-37 · Zbl 1029.68549 |
| [17] | Durand, B., Inversion of 2D cellular automata: Some complexity results, Theoretical Computer Science, 134, 2, 387-401 (1994) · Zbl 0938.68737 |
| [18] | Eubank, S.; Guclu, H.; Anil Kumar, V.; Marathe, M.; Srinivasan, A.; Toroczkai, Z.; Wang, N., Modelling disease outbreaks in realistic urban social networks, Nature, 429, 180-184 (2004) |
| [19] | Epstein, J., Generative Social Science: Studies in Agent-Based Computational Modeling (2007), Princeton University Press: Princeton University Press Princeton, NJ |
| [20] | Floreen, P.; Orponen, P., Attraction radii in Hopfield nets are hard to compute, Neural Computation, 5, 5, 812-821 (1993) |
| [21] | P. Floreen, P. Orponen, Complexity issues in discrete Hopfield networks, Research Report No. A-1994-4, Department of Computer Science, University of Helsinki, 1994; P. Floreen, P. Orponen, Complexity issues in discrete Hopfield networks, Research Report No. A-1994-4, Department of Computer Science, University of Helsinki, 1994 · Zbl 0727.68043 |
| [22] | Freedman, M., Limits, logic and computation, Proceedings of the National Academy of Sciences of the United States of America, 95, 95-97 (1998) · Zbl 0891.68041 |
| [23] | Garzon, M., Models of massive parallelism: Models of cellular automata and neural networks, (EATCS Monographs on Theoretical Computer Science (1995), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0844.68041 |
| [24] | Gouda, M.; Chang, C., Proving liveness for networks of communicating finite state machines, ACM Transactions on Programming Languages and Systems, 8, 1, 154-182 (1986) · Zbl 0593.68016 |
| [25] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co.: W.H. Freeman and Co. San Francisco, CA · Zbl 0411.68039 |
| [26] | Green, F., NP-Complete problems in cellular automata, Complex Systems, 1, 3, 453-474 (1987) · Zbl 0648.68067 |
| [27] | (Gutowitz, H., Cellular Automata: Theory and Experiments (1989), North Holland: North Holland Amsterdam) · Zbl 1455.68111 |
| [28] | Harel, D.; Kupferman, O.; Vardi, M. Y., On the complexity of verifying concurrent transition systems, Information and Computation, 173, 2, 143-161 (2002) · Zbl 1009.68082 |
| [29] | Hunt, H.; Marathe, M.; Radhakrishnan, V.; Stearns, R., The complexity of planar counting problems, SIAM Journal on Computing, 27, 4, 1142-1167 (1998) · Zbl 0911.68060 |
| [30] | Höfting, F.; Lengauer, T.; Wanke, E., Processing of hierarchically defined graphs and graph families, (Data Structures and Efficient Algorithms (Final Report on the DFG Special Joint Initiative). Data Structures and Efficient Algorithms (Final Report on the DFG Special Joint Initiative), Lecture Notes in Computer Science, vol. 594 (1992), Springer-Verlag: Springer-Verlag Berlin), 44-69 |
| [31] | Hunt, H.; Marathe, M.; Rosenkrantz, D.; Stearns, R., Towards a predictive complexity theory for periodically specified problems, (Istrate, G.; Percus, A.; Moore, C., Computational Complexity and Statistical Physics (2006), Oxford University Press: Oxford University Press New York, NY), 285-317 · Zbl 1156.82357 |
| [32] | H. Hunt III, M. Marathe, R. Stearns, Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures, in: Proc. Intl. Conf. Symbolic and Algebraic Computation, ISSAC 2001, London, Ontario, July 2001, pp. 183-191; H. Hunt III, M. Marathe, R. Stearns, Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures, in: Proc. Intl. Conf. Symbolic and Algebraic Computation, ISSAC 2001, London, Ontario, July 2001, pp. 183-191 · Zbl 1356.68279 |
| [33] | H. Hunt III, R. Stearns, M. Marathe, Relational representability, local reductions and the complexity of generalized satisfiability problems, Technical Report No. LA-UR-00-6108, Los Alamos National Laboratory, April 2001; H. Hunt III, R. Stearns, M. Marathe, Relational representability, local reductions and the complexity of generalized satisfiability problems, Technical Report No. LA-UR-00-6108, Los Alamos National Laboratory, April 2001 · Zbl 1356.68279 |
| [34] | Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, Journal of Computer and System Sciences, 63, 4, 512-530 (2001) · Zbl 1006.68052 |
| [35] | Kschischang, F.; Frey, B.; Loeliger, H., Factor graphs and the sum-product algorithm, IEEE Transactions on Information Theory, 47, 2, 498-519 (2001) · Zbl 0998.68234 |
| [36] | D. Kempe, J. Kleinberg, E. Tardos, Influential nodes in a diffusion model for social networks, in: Proc. 32nd International Colloquium on Automata, Languages and Programming, ICALP 2005, Lisbon, Portugal, July 2005, pp. 1127-1138; D. Kempe, J. Kleinberg, E. Tardos, Influential nodes in a diffusion model for social networks, in: Proc. 32nd International Colloquium on Automata, Languages and Programming, ICALP 2005, Lisbon, Portugal, July 2005, pp. 1127-1138 · Zbl 1084.91053 |
| [37] | Kohavi, Z., Switching and Finite Automata Theory (1970), McGraw-Hill: McGraw-Hill New York, NY · Zbl 0206.47701 |
| [38] | S. Khanna, M. Sudan, L. Trevisan, Constraint satisfaction: The approximability of minimization problems, in: Proc. 12th IEEE Annual Conference on Computational Complexity, CCC’97, Ulm, Germany, June 1997, pp. 282-291; S. Khanna, M. Sudan, L. Trevisan, Constraint satisfaction: The approximability of minimization problems, in: Proc. 12th IEEE Annual Conference on Computational Complexity, CCC’97, Ulm, Germany, June 1997, pp. 282-291 |
| [39] | Kung, H., Why systolic architectures, IEEE Computer, 15, 1, 37-42 (1982) |
| [40] | Laubenbacher, R.; Pareigis, B., Decomposition and simulation of sequential dynamical systems, Advances in Applied Mathematics, 30, 4, 655-678 (2003) · Zbl 1027.37049 |
| [41] | Laubenbacher, R.; Pareigis, B., Equivalence relations on finite dynamical systems, Advances in Applied Mathematics, 26, 3, 237-251 (2001) · Zbl 0986.37028 |
| [42] | Laubenbacher, R.; Stigler, B., A computational algebra approach to the reverse engineering of gene regulatory networks, Journal of Theoretical Biology, 229, August, 523-537 (2004) · Zbl 1440.92032 |
| [43] | M. Mahajan, Studies in language classes defined by different types of time-varying cellular automata, Ph.D. Thesis, Indian Institute of Technology, Madras, India, 1992; M. Mahajan, Studies in language classes defined by different types of time-varying cellular automata, Ph.D. Thesis, Indian Institute of Technology, Madras, India, 1992 |
| [44] | N. Margolus, An embedded DRAM architecture for large-scale spatial-lattice computations, in: Proc. 27th Annual Intl. Symp. Computer Architecture, ISCA 2000, Vancouver, Canada, June 2000, pp. 149-160; N. Margolus, An embedded DRAM architecture for large-scale spatial-lattice computations, in: Proc. 27th Annual Intl. Symp. Computer Architecture, ISCA 2000, Vancouver, Canada, June 2000, pp. 149-160 |
| [45] | M. Marathe, Towards a predictive computational complexity theory, in: Proc. International Colloquium on Automata Languages and Programming, ICALP 2002, Malaga, Spain, July 2002, pp. 22-31; M. Marathe, Towards a predictive computational complexity theory, in: Proc. International Colloquium on Automata Languages and Programming, ICALP 2002, Malaga, Spain, July 2002, pp. 22-31 · Zbl 1056.68546 |
| [46] | N. Margolus, Architecture for DRAM-based systolic computations, in: Proc. IEEE Workshop on FPGAs for Custom Computing Machines, Napa Valley, CA, April 1997, pp. 2-11; N. Margolus, Architecture for DRAM-based systolic computations, in: Proc. IEEE Workshop on FPGAs for Custom Computing Machines, Napa Valley, CA, April 1997, pp. 2-11 |
| [47] | Mortveit, H.; Reidys, C., Discrete sequential dynamical systems, Discrete Mathematics, 226, 1-3, 281-295 (2001) · Zbl 1004.05056 |
| [48] | Macy, M. W.; Willer, R., From factors to actors: Computational sociology and agent-based modeling, Annual Review of Sociology, 28, 143-166 (2002) |
| [49] | Berry, B.; Kiel, L.; Elliott, E., Adaptive agents, intelligence, and emergent human organization: Capturing complexity through agent-based modeling, Proceedings of the National Academy of Sciences, 99, Suppl. 3 (2002), (special issue) |
| [50] | Newman, M., The structure and function of complex networks, SIAM Review, 45, 2, 167-256 (2003) · Zbl 1029.68010 |
| [51] | C. Nichitiu, E. Remila, Simulations of graph automata, in: Proc. Satellite Workshop on Graph Automata held in conjunction with the conference on Mathematical Foundations of Computer Science, MFCS’98, Brno, Czech Republic, August 1998; C. Nichitiu, E. Remila, Simulations of graph automata, in: Proc. Satellite Workshop on Graph Automata held in conjunction with the conference on Mathematical Foundations of Computer Science, MFCS’98, Brno, Czech Republic, August 1998 · Zbl 0941.68640 |
| [52] | Orponen, P., Computational complexity of neural networks: A survey, Nordic Journal of Computing, 1, 1, 94-110 (1994) |
| [53] | P. Orponen, An overview of the computational power of recurrent neural networks, in: Proc. 9th Finnish AI Conference STeP 2000 — Millennium of AI, Espoo, Finland, 2000, pp. 89-96; P. Orponen, An overview of the computational power of recurrent neural networks, in: Proc. 9th Finnish AI Conference STeP 2000 — Millennium of AI, Espoo, Finland, 2000, pp. 89-96 |
| [54] | Peng, W., Deadlock detection in communicating finite state machines by even reachability analysis, Mobile Networks and Applications, 2, 3, 251-257 (1997) |
| [55] | Reidys, C., On acyclic orientations and sequential dynamical systems, Advances in Applied Mathematics, 27, 4, 790-804 (2001) · Zbl 1017.68144 |
| [56] | Roka, Z., One-way cellular automata on Cayley graphs, Theoretical Computer Science, 132, 1-2, 259-290 (1994) · Zbl 0821.68087 |
| [57] | Rabinovich, A., Complexity of equivalence problems for concurrent systems of finite agents, Information and Computation, 127, 2, 164-185 (1997) |
| [58] | Stearns, R.; Hunt, H., Power indices and easier hard problems, Mathematical Systems Theory, 23, 4, 209-225 (1990) · Zbl 0719.68025 |
| [59] | S. Shukla, H. Hunt III, D. Rosenkrantz, R. Stearns, On the complexity of relational problems for finite state processes, in: International Colloquium on Automata Programming and Languages, ICALP 1996, Paderborn, Germany, July 1996, pp. 466-477; S. Shukla, H. Hunt III, D. Rosenkrantz, R. Stearns, On the complexity of relational problems for finite state processes, in: International Colloquium on Automata Programming and Languages, ICALP 1996, Paderborn, Germany, July 1996, pp. 466-477 · Zbl 1046.68627 |
| [60] | T. Schaefer, The complexity of satisfiability problems, in: Proc. 10th ACM Symposium on Theory of Computing, STOC’78, San Diego, CA, May 1978, pp. 216-226; T. Schaefer, The complexity of satisfiability problems, in: Proc. 10th ACM Symposium on Theory of Computing, STOC’78, San Diego, CA, May 1978, pp. 216-226 · Zbl 1282.68143 |
| [61] | Sarkar, P., A brief history of cellular automata, ACM Computing Surveys, 32, 1, 80-107 (2000) |
| [62] | Sima, J.; Orponen, P., General-purpose computation with neural networks: A survey of complexity theoretic results, Neural Computation, 15, 2727-2778 (2003) · Zbl 1097.68589 |
| [63] | Sutner, K., On the computational complexity of finite cellular automata, Journal of Computer and System Sciences, 50, 1, 87-97 (1995) · Zbl 0827.68078 |
| [64] | Sutner, K., Additive automata on graphs, Complex Systems, 2, 6, 649-661 (1988) · Zbl 0679.68107 |
| [65] | P. Tosic, G. Agha, On the computational complexity of counting fixed points in symmetric Boolean graph automata, in: Proc. Fourth Intl. Conf. Unconventional Computation, UC’05, Sevilla, Spain, October 2005, pp. 191-205; P. Tosic, G. Agha, On the computational complexity of counting fixed points in symmetric Boolean graph automata, in: Proc. Fourth Intl. Conf. Unconventional Computation, UC’05, Sevilla, Spain, October 2005, pp. 191-205 · Zbl 1161.68608 |
| [66] | P. Tosic, Counting fixed points and Gardens of Eden of sequential dynamical systems on planar bipartite graphs, in: Electronic Colloquium on Computational Complexity, ECCC-TR05-091, 2005; P. Tosic, Counting fixed points and Gardens of Eden of sequential dynamical systems on planar bipartite graphs, in: Electronic Colloquium on Computational Complexity, ECCC-TR05-091, 2005 · Zbl 1100.68072 |
| [67] | Tamassia, R.; Tollis, I. G., Planar grid embedding in linear time, IEEE Transactions on Circuits and Systems, 36, 9, 1230-1234 (1989) |
| [68] | Vadhan, S., The complexity of counting in sparse, regular and planar graphs, SIAM Journal on Computing, 31, 2, 398-427 (2001) · Zbl 0994.68070 |
| [69] | Valiant, L., The complexity of enumeration and reliability problems, SIAM Journal on Computing, 8, 3, 410-421 (1979) · Zbl 0419.68082 |
| [70] | L. Valiant, V. Vazirani, NP is as easy as detecting unique solutions, in: Proc. ACM Symp. on Theory of Computing, STOC’85, Newport, RI, May 1985, pp. 458-463; L. Valiant, V. Vazirani, NP is as easy as detecting unique solutions, in: Proc. ACM Symp. on Theory of Computing, STOC’85, Newport, RI, May 1985, pp. 458-463 · Zbl 0621.68030 |
| [71] | von zur Gathen, J., Parallel linear algebra, (Reif, J. H., Synthesis of Parallel Algorithms (1993), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Mateo, CA), 573-617, (Chapter 13) |
| [72] | (Wolfram, S., Theory and Applications of Cellular Automata (1987), World Scientific) |
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.
