论文标题
布尔网络中极限周期问题的复杂性
Complexity of limit-cycle problems in Boolean networks
论文作者
论文摘要
布尔网络是相互作用实体的通用模型，并应用于基因调节等生物学现象。吸引者扮演着核心角色，实体更新时间表是未知的先验。本文介绍了与更新时间表的存在有关的问题的计算复杂性，以使某些限制周期长度可能是可能的。我们首先证明，给定一个并行更新的布尔网络，知道它至少具有一个限制周期$ k $的限制周期是$ \ text {np} $ - 完整。在块序列更新时间表上添加生存量化不会改变问题的复杂性类别，但是以下交替使我们在多项式层次结构中以上一个级别：鉴于布尔网络，知道是否存在块序列更新时间表，以使其长度$ k $ k $ k $ are $ nemency $ k $ are $ nement $ k $是$σ_2^\ fext text pext text pe text pe text p} $ -
Boolean networks are a general model of interacting entities, with applications to biological phenomena such as gene regulation. Attractors play a central role, and the schedule of entities update is a priori unknown. This article presents results on the computational complexity of problems related to the existence of update schedules such that some limit-cycle lengths are possible or not. We first prove that given a Boolean network updated in parallel, knowing whether it has at least one limit-cycle of length $k$ is $\text{NP}$-complete. Adding an existential quantification on the block-sequential update schedule does not change the complexity class of the problem, but the following alternation brings us one level above in the polynomial hierarchy: given a Boolean network, knowing whether there exists a block-sequential update schedule such that it has no limit-cycle of length $k$ is $Σ_2^\text{P}$-complete.
