第4章　基于细胞分裂的类组织时间膜系统计算效率

类组织膜系统是一类受细胞之间物质交流启发而形成的生物计算系统。受到细胞可以通过有丝分裂进行繁殖的生物实际启发，文献［1］首次提出基于细胞分裂的类组织膜系统，可以在线性时间内生成指数级数量的细胞。这为类组织膜系统在有效时间内求解NP完全问题提供了理论基础。该文献还使用基于细胞分裂的类组织膜系统首次在多项式时间内求解了SAT问题。随后，带细胞分裂的类组织膜系统也解决了其他NP难问题，例如三着色问题［2-4］，旅行商问题［5］，顶点覆盖问题［6］等。

作为一个典型的NP完全问题，SAT问题在类细胞膜系统中已被广泛研究，但在类组织膜系统中却很少涉及。在文献［7］和［8］中，构造了类组织膜系统在多项式时间内求解SAT问题。在这些研究成果中，都假设系统中每条规则具有一个精确且相同的执行时间，然而，细胞中生化反应的执行时间是不可控的。因此，考虑在时间无关模式下建立鲁棒性能优异的膜系统，并对相关的NP难问题进行求解，具有重要研究价值。在时间无关模式下，已经有文献对子集和问题以及哈密尔顿路径问题等进行了求解［9-11］，但目前还没有涉及构造时间膜系统求解SAT问题。

本章针对SAT问题对类组织时间膜系统的计算效率进行研究，引入细胞分裂方法证明了该类系统可以在多项式时间内求解SAT问题，并且通信规则的最大长度仅为3。该系统可以解决任意大小的实例，且规则的执行时间长短对计算结果没有任何影响。最后，本章给出了一个具体实例来说明建立的膜系统是如何工作的。