1. Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs.
- Author
-
Kawachi, Akinori, Ogihara, Mitsunori, and Uchizawa, Kei
- Subjects
- *
BOOLEAN algebra , *FINITE element method , *ALGORITHMS , *NUMERICAL analysis , *DYNAMICAL systems - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF