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

Simple item page
dc.creatorKosub, Sven
dc.date2008-01-24
dc.date2008-12-01
dc.date.accessioned2026-07-07T12:05:38Z
dc.date.available2026-07-07T12:05:38Z
dc.descriptionA 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.
dc.description17 pages; this version corrects an error/typo in the 2008/01/24 version
dc.identifierhttps://arxiv.org/abs/0801.3802
dc.identifierhttp://arxiv.org/abs/0801.3802
dc.identifierMathematics in Computer Science, 1(3):487-505, 2008, special issue on Modeling and Analysis of Complex Systems
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/208427
dc.subjectComputational Complexity
dc.subjectDisordered Systems and Neural Networks
dc.subjectDiscrete Mathematics
dc.subjectAdaptation and Self-Organizing Systems
dc.subjectCellular Automata and Lattice Gases
dc.subjectF.2.2; F.1.1; F.1.3
dc.titleDichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems
dc.typetext

Files

Collections

arXiv