Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems

摘要

A complete classification of the computational complexity of the fixed-point existence problem for Boolean dynamical systems, i.e., finite discrete dynamical systems over the domain {0, 1}, is presented. For function classes ${mathcal{F}}$ and graph classes ${mathcal{G}}$ , an ( ${mathcal{F}},{mathcal{G}}$ )-system is a Boolean dynamical system such that all local transition functions lie in ${mathcal{F}}$ and the underlying graph lies in ${mathcal{G}}$ . Let ${mathcal{F}}$ be a class of Boolean functions which is closed under composition and let ${mathcal{G}}$ be a class of graphs which is closed under taking minors. The following dichotomy theorems are shown: (1) If ${mathcal{F}}$ contains the self-dual functions and ${mathcal{G}}$ contains the planar graphs, then the fixed-point existence problem for ( ${mathcal{F}},{mathcal{G}}$ )-systems with local transition function given by truth-tables is NP-complete; otherwise, it is decidable in polynomial time. (2) If ${mathcal{F}}$ contains the self-dual functions and ${mathcal{G}}$ contains the graphs having vertex covers of size one, then the fixed-point existence problem for ( ${mathcal{F}},{mathcal{G}}$ )-systems with local transition function given by formulas or circuits is NP-complete; otherwise, it is decidable in polynomial time.