论文标题
布尔网络中固定点计数问题的复杂性
Complexity of fixed point counting problems in Boolean Networks
论文作者
论文摘要
带有$ n $组件的布尔网络（BN）是一个离散的动力系统，该系统由函数$ f的连续迭代描述：\ {0,1 \}^n \ to \ to \ {0,1 \}^n $。该模型在生物学中找到了应用，其中固定点起着核心作用。例如，在遗传法规中，它们对应于细胞表型。在这种情况下，实验揭示了组件之间的正面或负面影响：组件$ i $对组件$ j $的正（分别为负）影响$ j $，这意味着$ j $倾向于模仿（分别为否）$ i $。影响力的挖掘被称为签名的交互挖掘图（SID），一个SID可能对应大量BN（平均而言，根据$ n $的指数为双重指数）。目前的工作对BNS中固定点的良好研究开辟了新的观点。当生物学家发现国阵的SID时，他们可能会问：鉴于SID，它可以与至少/最多/最多$ K $固定点的BN对应吗？取决于输入，我们证明这些问题在$ \ textrm {p} $中或以$ \ textrm {np} $，$ \ textrm {np}^{\ textrm {np {np}} $，$ \ textrm { $ \ textrm {nexptime} $。特别是，我们证明它是$ \ textrm {np} $ - 完整（分别为$ \ textrm {nexptime} $ - 完整），以决定给定的SID是否可以与至少两个固定点的BN相对应（无固定点）。
A 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).
