## Barrett, Christopher L. and Hunt, Harry, and Marathe, Madhav V. and Ravi, S. S. and Rosenkrantz, Daniel J.et al. - Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.

dmtcs:2314 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03)
Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.

Authors: Barrett, Christopher L. and Hunt, Harry, and Marathe, Madhav V. and Ravi, S. S. and Rosenkrantz, Daniel J. and Stearns, Richard E.

A class of finite discrete dynamical systems, called Sequential Dynamical Systems (SDSs), was introduced in [BR99] as a formal model for analyzing simulation systems. Here, we address the complexity of two basic problems and their generalizations for SDSs.Given an SDS $\mathcal{S}$ and a configuration $\mathcal{C}$, the PREDECESSOR EXISTENCE (or PRE) problem is to determine whether there is a configuration $\mathcal{C}'$ such that $\mathcal{S}$ has a transition from $\mathcal{C}'$ to $\mathcal{C}$. Our results provide separations between efficiently solvable and computationally intractable instances of the PRE problem. For example, we show that the PRE problem can be solved efficiently for SDSs with Boolean state values when the node functions are symmetric and the underlying graph is of bounded tree width. In contrast, we show that allowing just one non-symmetric node function renders the problem $\mathbf{NP}$-complete even when the underlying graph is a star (which has a tree width of 1). Our results extend some of the earlier results by Sutner [Su95] and Green [Gr87] on the complexity of the PREDECESSOR EXISTENCE problem for 1-dimensional cellular automata.Given two configurations $\mathcal{C}$ and $\mathcal{C}'$ of a partial SDS $\mathcal{S}$, the PERMUTATION EXISTENCE (or PME) problem is to determine whether there is a permutation of nodes such that $\mathcal{S}$ has a transition from $\mathcal{C}'$ to $\mathcal{C}$ in one step. We show that the PME problem is $\mathbf{NP}$-complete even when the function associated with each node is a simple-threshold function. We also show that the problem can be solved efficiently for SDSs whose underlying graphs are of bounded degree and bounded tree width. We consider a generalized version (GEN-PME) of the PME problem and show that the problem is $\mathbf{NP}$-complete for SDSs where each node function is NOR and the underlying graph has a maximum node degree of 3. When each node computes the OR function or when each node computes the AND function, we show that the GEN-PME problem is solvable in polynomial time.

Source : oai:HAL:hal-01183322v1
Volume: DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03)
Section: Proceedings
Published on: January 1, 2003
Submitted on: November 21, 2016
Keywords: Computational Complexity,Discrete Dynamical Systems,Cellular Automata,Predecessor Existence,Permutation Existence,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[NLIN.NLIN-CG] Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG]