第3章　膜上带蛋白的时间膜系统

活细胞内的很多生化反应会受到细胞膜上蛋白质的控制。受该生物过程启发，A.Pǎun等于2006年首次提出膜上带蛋白的膜系统［1］。作为类细胞膜系统中的一种变体，该系统中膜内对象在膜上蛋白质的控制下完成进化。虽然这类系统提出时间较早，但目前的研究成果不多。对于一些典型的研究成果，例如在文献［2］中，膜上带蛋白膜系统仅使用一个膜就构建了计算通用的膜系统。当引入分裂规则后，这类系统可以在多项式时间（甚至线性时间）内求解NP完全问题，例如SAT问题［3］、QSAT问题［4］。

但是，目前的研究过程中均采用系统中每条规则仅有一个精确且相同的执行时间的假设，这使得现有膜系统的鲁棒性和容错性都不够优异。因此，有必要构造出一个与规则的执行时间无关，具有良好鲁棒性和容错性的生物计算系统，即膜上带蛋白的时间膜系统。最近，有学者通过膜上带蛋白的膜系统来求解NP完全问题［5］，但是结果显示系统的计算效率提高不够显著。随着对膜上带蛋白膜系统进一步研究，从生物学角度来看，一个膜上的蛋白质可以有多种，但对于其中的一种蛋白质，其可达状态只能在几种有限的状态之间转移。从该生物实际出发，有学者提出触发型膜上带蛋白膜系统，其中膜上每一类蛋白质仅有两种可达状态，其工作模式类似于触发器。这类膜系统的概念提出以后，其通用性在文献［6-7］中进行了研究，但是该模型在时间无关模式下计算效率的研究还尚未涉及。

本章首先基于膜上带蛋白的膜系统，构造了统一的方法在多项式时间内求解SAT问题。该方法采用基本膜分裂，且系统中进化规则的最大长度仅为4。该证明结果优化了文献［5］中的结论，获得了更好的计算效率。然后，本章将时间无关引入触发型膜上带蛋白的膜系统，并证明了SAT问题可以被一族触发型膜上带蛋白的时间膜系统以统一的方式在多项式时间内求解，系统中规则的执行时间长短对计算结果没有任何影响。