Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions
Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions
复制标题
XOR 函数有向图上的同步布尔有限动力系统
DOI：
10.1007/s00224-022-10111-x
复制
发表时间：
2022
影响因子：
0.5
通讯作者：
Uchizawa K.
中科院分区：
文献类型：
--
作者：
Ogihara M.;Uchizawa K.
在本文中，我们研究了在同步布尔有限动态系统上定义的许多计算问题的复杂性，其中更新函数是从异或及其否定的模板集中选择的。我们首先证明，如果对象执行排列，则可达性和路径相交问题在对数空间均匀 AC1 中是可解的，而已知可达性问题在 P 中，路径相交问题一般在 UP 中。我们还探讨了在对象子集上测试可达性或交集的情况，并表明这会加剧问题的复杂性：如果我们进一步要求交集的普遍性，那么这两个问题都将成为 NP 完全问题，甚至甚至是完全问题。接下来我们考虑精确循环长度问题，即确定是否存在在配置空间中产生具有精确给定长度的循环的初始配置，并证明该问题是NP完全问题。最后，我们考虑 t-前身问题和 t-伊甸园问题，并证明即使 t 的值也以二进制形式作为实例的一部分给出，这些问题也可以在多项式时间内求解，并且如果 t 的值以一元形式作为实例的一部分给出，则这两个问题在对数空间一致 NC2 中。
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 AC1if 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-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 thet-predecessor andt-Garden of Eden problem, and prove that these are solvable in polynomial time even if the value oftis also given in binary as part of instance, and the two problems are in logarithmic space-uniform NC2if the value oftis given in unary as part of instance.