Discrete Mathematics & Theoretical Computer Science (Jan 2003)
Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.
Abstract
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.
Keywords
