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:
- 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).
- 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