Abstract
Sequential Dynamical Systems (SDSs) serve as a formal framework for modeling complex computer simulations, such as urban traffic flows. This paper investigates the properties of two specific configuration types within SDSs: Garden of Eden (GE) configurations and Fixed Points (FP). We establish that while the non-existence of GE configurations in finite domains is tied to the "self-essential" property of local functions, this condition is sufficient but not necessary for infinite domains. Furthermore, we analyze the computational complexity of the Fixed Point Existence (FPE) problem, proving it is NP-complete for several simple classes of SDSs while identifying specific functional classes—such as linear and monotone functions—where the problem remains efficiently solvable.
Introduction
Sequential Dynamical Systems (SDSs) were introduced to provide a rigorous mathematical foundation for large-scale simulations, most notably the Transportation Analysis and Simulation System (TRANSIMS). Unlike traditional Cellular Automata, where all nodes update their states simultaneously, an SDS updates its nodes according to a specific sequence or permutation. This dependency on update order introduces significant complexity into the system's phase space—the mapping of all possible state transitions.
This research focuses on two critical aspects of SDS phase space:
- Garden of Eden (GE) Configurations: States that lack a predecessor and thus can only be reached if they are the initial state.
- Fixed Points (FP): States that remain invariant under the system's transition function.
Garden of Eden Configurations
A configuration is a Garden of Eden if no other state maps to it; it has no "pre-image" in the phase space. In systems with finite state domains, previous research established that a GE configuration exists if and only if the system is not invertible. A key finding in this work relates to "self-essential" functions—local transition functions where a node's next state is always dependent on its current state.
In finite domains, if every local function in an SDS is self-essential, the system is guaranteed to have no GE configurations. However, this paper demonstrates that for systems with infinite domains, self-essentiality is a sufficient but not a necessary condition. This distinction highlights the unique topological challenges presented by infinite state spaces in dynamical systems compared to their finite counterparts.
The Fixed Point Existence (FPE) Problem
A configuration $C$ is a fixed point if the transition out of $C$ leads back to $C$ itself. A notable property of SDSs is that a fixed point remains a fixed point regardless of the update order $\pi$. Despite this inherent stability, determining whether a fixed point exists—the FPE problem—is computationally demanding.
Complexity Results
The authors prove that the FPE problem is NP-complete, even when the local transition functions are restricted to simple symmetric Boolean functions. By employing a reduction from ODD-PE3SAT (a variant of the 3-Satisfiability problem), the paper shows that FPE is hard for SDSs using functions from the following sets:
- {NAND, XNOR}
- {NAND, XOR}
- {NOR, XNOR}
- {NOR, XOR}
This result is significant because it demonstrates that global complexity and unpredictability can emerge from very simple, symmetric local interactions.
Efficiently Solvable Classes
While the general FPE problem is hard, the paper identifies several classes of SDSs where fixed points can be found in polynomial time:
- Linear Systems: If local functions are linear, fixed points can be identified using standard linear algebra techniques.
- Monotone Systems: For systems where local functions are monotone (i.e., increasing inputs never decrease the output), a fixed point is guaranteed to exist. These can be found in $O(m \cdot |D|)$ time, where $m$ is the number of edges and $|D|$ is the domain size.
- Restricted Boolean Sets: For SDSs using only {AND, OR, NAND, NOR}, the FPE problem is solvable in linear time ($O(n)$).
Conclusion and Future Work
This work clarifies the boundaries between tractability and NP-completeness in the analysis of Sequential Dynamical Systems. By characterizing the conditions for Garden of Eden configurations and the complexity of finding fixed points, the authors provide essential tools for researchers designing and analyzing complex simulations.
Several avenues for future research remain, including a complete characterization of GE configurations for infinite domains and exploring the complexity of "Strong Gardens of Eden"—states that are unreachable regardless of the specific update sequence chosen. Additionally, extending these results to non-symmetric functions may reveal further insights into the relationship between local rules and global system behavior.
Summary updated