Dichotomy results for fixed point counting in boolean dynamical systems

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from http://ritdml.rit.edu/handle/1850/9085 to RIT Scholar Works http://scholarworks.rit.edu/other/95, please update your feeds & links!
Title: Dichotomy results for fixed point counting in boolean dynamical systems
Author: Homan, Christopher; Kosub, Suen
Abstract: We present dichotomy theorems regarding the computational complexity of counting fixed points in boolean (discrete) dynamical systems, i.e., finite discrete dynamical systems over the domain {0, 1}. For a class F of boolean functions and a class G of graphs, an (F, G)-system is a boolean dynamical system with local transitions functions lying in F and graphs in G. We show that, if local transition functions are given by lookup tables, then the following complexity classification holds: Let F be a class of boolean functions closed under superposition and let G be a graph class closed under taking minors. If F contains all min-functions, all max-functions, or all self-dual and monotone functions, and G contains all planar graphs, then it is #Pcomplete to compute the number of fixed points in an (F, G)-system; otherwise it is computable in polynomial time. We also prove a dichotomy theorem for the case that local transition functions are given by formulas (over logical bases). This theorem has a significantly more complicated structure than the theorem for lookup tables. A corresponding theorem for boolean circuits coincides with the theorem for formulas.
Description: A preliminary version of this paper was presented at the 10th Italian Conference on Theoretical Computer Science (ICTCS’07).
Record URI: http://hdl.handle.net/1850/9085
Date: 2007

Files in this item

Files Size Format View
CHomanConfProc10-2007.pdf 235.7Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML

Advanced Search