Computer Science – Computational Complexity
Scientific paper
2008-01-24
Mathematics in Computer Science, 1(3):487-505, 2008, special issue on Modeling and Analysis of Complex Systems
Computer Science
Computational Complexity
17 pages; this version corrects an error/typo in the 2008/01/24 version
Scientific paper
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 F and graph classes G, an (F, G)-system is a boolean dynamical system such that all local transition functions lie in F and the underlying graph lies in G. Let F be a class of boolean functions which is closed under composition and let G be a class of graphs which is closed under taking minors. The following dichotomy theorems are shown: (1) If F contains the self-dual functions and G contains the planar graphs then the fixed-point existence problem for (F, G)-systems with local transition function given by truth-tables is NP-complete; otherwise, it is decidable in polynomial time. (2) If F contains the self-dual functions and G contains the graphs having vertex covers of size one then the fixed-point existence problem for (F, G)-systems with local transition function given by formulas or circuits is NP-complete; otherwise, it is decidable in polynomial time.
No associations
LandOfFree
Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-283547