论文标题
限制周期的复杂性与结合网络中的块序列更新时间表
Complexity of limit cycles with block-sequential update schedules in conjunctive networks
论文作者
论文摘要
在本文中，我们解决了以下决策问题：鉴于由其交互作用图定义的连接布尔网络，它的限制周期是否为给定长度k？如果k是问题的参数，则我们证明此问题通常是NP完整的。 $ k $是一个常数的情况，但是相互作用的挖掘没有强烈连接仍然打开。此外，我们研究了决策问题的变化：鉴于连接性的布尔网络，是否存在块 - 序列（分别为顺序）更新时间表，以使长度k的限制周期存在？我们证明，对于任何常数k> = 2，此问题都是NP算法。
In this paper, we deal the following decision problem: given a conjunctive Boolean network defined by its interaction digraph, does it have a limit cycle of a given length k? We prove that this problem is NP-complete in general if k is a parameter of the problem and in P if the interaction digraph is strongly connected. The case where $k$ is a constant, but the interaction digraph is not strongly connected remains open. Furthermore, we study the variation of the decision problem: given a conjunctive Boolean network, does there exist a block-sequential (resp. sequential) update schedule such that there exists a limit cycle of length k? We prove that this problem is NP-complete for any constant k >= 2.
