Complexity of fixed point counting problems in Boolean Networks

43 pagesA Boolean network (BN) with $n$ components is a discrete dynamical system described by the successive iterations of a function $f:\{0,1\}^n \to \{0,1\}^n$. This model finds applications in biology, where fixed points play a central role. For example, in genetic regulations, they correspond to cell phenotypes. In this context, experiments reveal the existence of positive or negative influences among components: component $i$ has a positive (resp. negative) influence on component $j$ meaning that $j$ tends to mimic (resp. negate) $i$. The digraph of influences is called signed interaction digraph (SID), and one SID may correspond to a large number of BNs (which is, in average, doubly exponential according to $n$). The present work opens a new perspective on the well-established study of fixed points in BNs. When biologists discover the SID of a BN they do not know, they may ask: given that SID, can it correspond to a BN having at least/at most $k$ fixed points? Depending on the input, we prove that these problems are in $\textrm{P}$ or complete for $\textrm{NP}$, $\textrm{NP}^{\textrm{NP}}$, $\textrm{NP}^{\textrm{#P}}$ or $\textrm{NEXPTIME}$. In particular, we prove that it is $\textrm{NP}$-complete (resp. $\textrm{NEXPTIME}$-complete) to decide if a given SID can correspond to a BN having at least two fixed points (resp. no fixed point)