Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems |
| |
Authors: | Sven Kosub |
| |
Affiliation: | 1. Fakult?t für Informatik, Technische Universit?t München, Boltzmannstra?e 3, D-85748, Garching, Germany
|
| |
Abstract: | 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 and graph classes , an ()-system is a Boolean dynamical system such that all local transition functions lie in and the underlying graph lies in . Let be a class of Boolean functions which is closed under composition and let be a class of graphs which is closed under taking minors. The following dichotomy theorems are shown: (1) If contains the self-dual functions and contains the planar graphs, then the fixed-point existence problem for ()-systems with local transition function given by truth-tables is NP-complete; otherwise, it is decidable in polynomial time. (2) If contains the self-dual functions and contains the graphs having vertex covers of size one, then the fixed-point existence problem for ()-systems with local transition function given by formulas or circuits is NP-complete; otherwise, it is decidable in polynomial time. |
| |
Keywords: | 68Q17 68Q80 68Q85 68R10 |
本文献已被 SpringerLink 等数据库收录! |
|