Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions

• Published in: Theory of computing systems 2023-06, Vol.67 (3), p.569-591
• Main Authors: Ogihara, M., Uchizawa, K.
• Format: Article
• Language: English
• Subjects: Boolean; Commemorative Issue for Alan L. Selman; Complexity; Computer Science; Dynamical systems; Graph theory; Intersections; Logarithms; Permutations; Polynomials; Theory of Computation
• ISSN: 1432-4350; 1433-0490
• DOI: 10.1007/s00224-022-10111-x

In this paper, we investigate the complexity of a number of computational problems defined on a synchronous boolean finite dynamical system, where update functions are chosen from a template set of exclusive-or and its negation. We first show that the reachability and path-intersection problems are solvable in logarithmic space-uniform AC 1 if the objects execute permutations, while the reachability problem is known to be in P and the path-intersection problem to be in UP in general. We also explore the case where the reachability or intersection are tested on a subset of objects, and show that this hardens complexity of the problems: both problems become NP-complete, and even π 2 p -complete if we further require universality of the intersection. We next consider the exact cycle length problem, that is, determining whether there exists an initial configuration that yields a cycle in the configuration space having exactly a given length, and show that this problem is NP-complete. Lastly, we consider the t -predecessor and t -Garden of Eden problem, and prove that these are solvable in polynomial time even if the value of t is also given in binary as part of instance, and the two problems are in logarithmic space-uniform NC 2 if the value of t is given in unary as part of instance.