论文标题
布尔网络中最小陷阱空间的计算复杂性
Computational Complexity of Minimal Trap Spaces in Boolean Networks
论文作者
论文摘要
布尔网络（BN）是由布尔函数定义的离散动力系统，该系统映射到域本身。 BN的陷阱空间是固定点的概括，其定义为由BN的功能封闭的子Hypercubes。如果陷阱空间不包含任何较小的陷阱空间，则最小。最小的陷阱空间具有分析具有各种更新模式的BNS吸引者的应用程序。本文确定了与最小陷阱空间相关的三个决策问题的计算复杂性结果：亚hypercube的陷阱空间属性的决策，其最小值的决定以及给定配置对最小陷阱空间的构件的决定。在一些有关布尔函数表示的情况下，我们研究了每个问题的计算复杂性。在一般情况下，我们证明了陷阱空间属性是综合的，最小值和成员资格属性为$π_2^{\ text P} $ - 完整。每当BN的本地函数要么是UNATE，要么使用真实表，二进制决策图或双DNF（PETRI NET编码）表示，因此复杂性在多项式层次结构中下降了一个级别：陷阱空间属性可以在多项式时间内决定，而决定最小值和成员的最小值和成员为CONP-OPTOR。当将BN作为其功能图时，所有这些问题都在P中。
A Boolean network (BN) is a discrete dynamical system defined by a Boolean function that maps to the domain itself. A trap space of a BN is a generalization of a fixed point, which is defined as the sub-hypercubes closed by the function of the BN. A trap space is minimal if it does not contain any smaller trap space. Minimal trap spaces have applications for the analysis of attractors of BNs with various update modes. This paper establishes the computational complexity results of three decision problems related to minimal trap spaces: the decision of the trap space property of a sub-hypercube, the decision of its minimality, and the decision of the membership of a given configuration to a minimal trap space. Under several cases on Boolean function representations, we investigate the computational complexity of each problem. In the general case, we demonstrate that the trap space property is coNP-complete, and the minimality and the membership properties are $Π_2^{\text P}$-complete. The complexities drop by one level in the polynomial hierarchy whenever the local functions of the BN are either unate, or are represented using truth-tables, binary decision diagrams, or double DNFs (Petri net encoding): the trap space property can be decided in a polynomial time, whereas deciding the minimality and the membership are coNP- complete. When the BN is given as its functional graph, all these problems are in P.
