Predecessor and Permutation Existence Problems for Sequential Dynamical Systems

Christopher L. Barrett, Harry B. Hunt Iii, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Richard Edwin StearnsDMCS 2003 · OpenReview

Abstract

Sequential Dynamical Systems (SDSs) serve as a formal framework for analyzing discrete simulation systems. This paper investigates the computational complexity of two fundamental problems: Predecessor Existence (PRE) and Permutation Existence (PME). We demonstrate that while these problems are generally $\mathbf{NP}$-complete, they become tractable under specific constraints related to node function symmetry and graph topology, such as bounded treewidth. Our results provide a clear separation between efficiently solvable and computationally intractable instances, extending earlier findings on cellular automata into the sequential domain.

Introduction

Sequential Dynamical Systems (SDSs) were introduced as a robust model for discrete simulations where components update sequentially rather than in parallel. Unlike Cellular Automata (CA), where all cells transition simultaneously, an SDS updates its nodes according to a specific permutation $\pi$. This sequential nature makes SDSs particularly suitable for modeling systems where the order of events is critical, such as traffic networks or social influence models. However, this flexibility introduces significant complexity when attempting to "reverse" the system or determine the underlying update sequence.

Problem Formulations

The research focuses on two primary computational challenges:

  1. Predecessor Existence (PRE): Given an SDS $\mathcal{S}$ and a configuration $\mathcal{C}$, does there exist a configuration $\mathcal{C}'$ such that $\mathcal{S}$ has a transition from $\mathcal{C}'$ to $\mathcal{C}$? This problem is central to understanding the reachability of states and identifying "Garden of Eden" configurations (states with no past).
  2. Permutation Existence (PME): Given two configurations $\mathcal{C}$ and $\mathcal{C}'$, does there exist a permutation $\pi$ of the nodes such that the system transitions from $\mathcal{C}'$ to $\mathcal{C}$ in one step? This asks if a specific state change is possible under any update order.

Complexity of Predecessor Existence

The complexity of the PRE problem is highly sensitive to the symmetry of the node functions and the structure of the underlying graph.

The Role of Symmetry

A node function is symmetric if its output depends only on the number of active inputs, not their specific positions. The authors find that symmetry acts as a critical threshold for complexity. For SDSs with Boolean states and symmetric node functions, the PRE problem is efficiently solvable if the underlying graph has bounded treewidth.

In a striking contrast, the problem becomes $\mathbf{NP}$-complete if even a single node function is non-symmetric, even on a "star" graph (a tree with treewidth 1). This highlights that the logic of individual nodes can outweigh the simplicity of the network structure.

Graph Topology and Treewidth

The paper utilizes tree decompositions to provide polynomial-time algorithms for graphs with bounded treewidth. By using dynamic programming, the state space can be explored locally within the "bags" of the tree decomposition, allowing for efficient global solutions. However, for more complex topologies like planar graphs, the PRE problem remains $\mathbf{NP}$-complete for $k$-threshold functions ($k \ge 2$).

Complexity of Permutation Existence

The PME problem asks whether the order of updates can explain an observed transition. This is shown to be $\mathbf{NP}$-complete even for simple-threshold functions on star graphs. This suggests that the update sequence is a powerful component of the system's behavior, making it difficult to reverse-engineer the rules of the simulation.

Generalized PME (GEN-PME)

The authors also consider a generalized version (GEN-PME) and establish a sharp complexity boundary based on the type of Boolean functions used:

  • Hard Cases: The problem is $\mathbf{NP}$-complete for systems where each node computes the NOR function, even with a maximum node degree of 3.
  • Easy Cases: The problem is solvable in polynomial time when all nodes compute either the OR function or the AND function.

Conclusion

This research maps the boundary between tractability and intractability for SDSs. The findings suggest a fundamental trade-off: computational efficiency in reverse-engineering these systems requires either highly structured (symmetric) local logic or a highly restricted (low treewidth) global topology. These results extend classical work by Sutner and Green on cellular automata, providing a theoretical foundation for the analysis of complex, sequential simulation models.

Summary updated

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.
BibTeX
@inproceedings{barrett2003predecessor,
  author = {Christopher L. Barrett and Harry B. Hunt III and Madhav V. Marathe and S. S. Ravi and Daniel J. Rosenkrantz and Richard Edwin Stearns},
  title = {{Predecessor and Permutation Existence Problems for Sequential Dynamical Systems}},
  booktitle = {DMCS},
  year = {2003},
  url = {https://openreview.net/forum?id=ZcqlzmmnV6},
}
Figure