Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
复制标题
有向图上布尔有限动力系统的广义前驱存在问题
DOI：
10.1016/j.tcs.2018.08.026
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Uchizawa Kei
中科院分区：
文献类型：
--
作者：
Kawachi Akinori;Ogihara Mitsunori;Uchizawa Kei
摘要 布尔有限同步动力系统（简称BFDS）由有限数量的对象组成，每个对象都维护一个布尔状态，在单独接收状态分配后，对象以离散时间步同步更新相对于对象特定的时间无关布尔函数的状态。本文研究了给定一个布尔有限同步动力系统、一个表示对象状态的布尔向量和一个正整数t的配置，确定是否存在另一种配置可以在t步中达到给定配置的计算复杂性。之前已经表明，如果对象的更新函数是任意扇入的合取或任意扇入的析取，则这个问题（我们称为 t 前驱问题）即使在 t= 1 时也是 NP 完全的。本文研究了各种允许更新函数集以及多项式有界 t 的 t 前驱问题的计算复杂性。它还研究了 t-Garden-Of-Eden 问题，这是 t-前驱问题的一个变体，该问题询问配置是否有 t-前驱，而该配置本身没有前驱。本文获得了除其中一个问题之外的所有问题的复杂性理论特征。
Abstract A Boolean Finite Synchronous Dynamical System (BFDS, for short) consists of a finite number of objects that each maintains a boolean state, where after individually receiving state assignments, the objects update their state with respect to object-specific time-independent boolean functions synchronously in discrete time steps. The present paper studies the computational complexity of determining, given a boolean finite synchronous dynamical system, a configuration, which is a boolean vector representing the states of the objects, and a positive integer t, whether there exists another configuration from which the given configuration can be reached in t steps. It was previously shown that this problem, which we call the t-Predecessor Problem, is NP-complete even for t= 1 if the update function of an object is either the conjunction of arbitrary fan-in or the disjunction of arbitrary fan-in. This paper studies the computational complexity of the t-Predecessor Problem for a variety of sets of permissible update functions as well as for polynomially bounded t. It also studies the t-Garden-Of-Eden Problem, a variant of the t-Predecessor Problem that asks whether a configuration has a t-predecessor, which itself has no predecessor. The paper obtains complexity theoretical characterizations of all but one of these problems.