License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.76
URN: urn:nbn:de:0030-drops-127543
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12754/
Ogihara, Mitsunori ;
Uchizawa, Kei
Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions
Abstract
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.
BibTeX - Entry
@InProceedings{ogihara_et_al:LIPIcs:2020:12754,
author = {Mitsunori Ogihara and Kei Uchizawa},
title = {{Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {76:1--76:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12754},
URN = {urn:nbn:de:0030-drops-127543},
doi = {10.4230/LIPIcs.MFCS.2020.76},
annote = {Keywords: Computational complexity, dynamical systems, Garden of Eden, predecessor, reachability}
}
|
Keywords: |
|
Computational complexity, dynamical systems, Garden of Eden, predecessor, reachability |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
