2026-07-26T02:38:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12754 2024-03-06T10:50:43Z ddc:004 open_access

Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions Ogihara, Mitsunori Uchizawa, Kei Computational complexity dynamical systems Garden of Eden predecessor reachability 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¹ 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 Π^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² if the value of t is given in unary as part of instance. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mitsunori Ogihara and Kei Uchizawa 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.76 urn:nbn:de:0030-drops-127543 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.76 eng https://creativecommons.org/licenses/by/3.0/legalcode