3.3 触发型膜上带蛋白的时间膜系统求解SAT问题
在定义1.2中，膜上每种蛋白质的可达状态并没有做任何限定，即在系统计算过程中每种蛋白质的可达状态可能是无限多个。下面考虑触发型蛋白膜系统（膜上每一类蛋白质仅有两种可达状态），将时间无关引入这类系统，并研究这类系统的计算有效性。
对于触发型膜上带蛋白的时间膜系统，其定义与定义1.2是类似的，只是膜上的蛋白质只能在两个状态之间进行跳转，这里就不再重新定义。不同的是，分裂规则和定义1.2是不一样的，因为触发型膜上带蛋白的时间膜系统膜上的蛋白质只有两种可达状态，因此分裂规则为
其中，原始膜可以为基本膜，也可以是非基本膜。蛋白质的两种可达状态为p和p′。受到膜h上蛋白质p及膜内对象a的影响，初始膜分裂为两个具有相同标签的膜。在此过程中原始膜上的蛋白质可能变化为另外一种蛋白质；同时，对象a进化为b和c分别进入两个产生的新膜中。原始膜内的其他物质都将被复制到新产生的两个膜内。
另外，对于进化规则，其形式基本上与定义2.1中的形式是一样的，不同的是，膜上的每种蛋白质只可能出现两种状态。对于触发型膜上带蛋白的时间膜系统中的进化规则，其长度包括规则中膜上蛋白质以及膜内对象的总数。在时间无关模式下，本章使用PMCFTPPM（k）表示使用触发型膜上带蛋白膜系统能在多项式时间内求出统一解的问题集合。其中，系统中进化规则的最大长度为k。
定理3.3：SAT问题可以通过一族触发型时间膜上带蛋白膜系统在多项式RS步内通过膜分裂以统一的方式解决。
证明：对于具有n个布尔变量和m个子句的公式，本章考虑命题公式γ＝C1∧C2∧…∧Cm，其中，Cj＝yj，1∨…∨yj，pj，yj，i ∈
≤k≤n｝，1≤j≤m，1≤i≤qj，
是命题变量xk的否定形式。
再通过以下多重集对γ进行编码，其中1≤j≤m，1≤i≤n
接下来，在时间无关模式下定义一族触发型膜上带蛋白的识别P系统，该系统可以处理提供输入多重集cod（γ）的所有例子γ。对于给定的含有n个变量和m个子句的布尔公式，该识别P系统构造如下：
其中，O为字母表：
对象ti，j表示变量xi的赋值为真（true），对象fi，j表示变量xi的赋值为假（false）；对象rj表示变量赋值使得子句j是可满足的；物质yes表示公式是可满足的，而物质no表示公式是不满足的；
P是蛋白质对象构成的集合：
另外，Σ＝｛Yi，j，Ni，j，Bi，j|1≤i≤n，1≤j≤m｝为在O内的输入字母表；μ＝［［［］3］2［］4］1为初始膜结构；w1＝no，w2＝a1，w3＝w4＝λ是各个膜内的初始物质；z1＝g，z2＝p1，…，pn，z3＝q，z4＝s是各个膜上初始状态下的蛋白质对象；iin＝3为输入膜；iout＝0是保存最后计算结果的输出区域；R1，…，R4表示区域1，2，3，4中规则的有限集，包含以下三个阶段的规则集。
（1）产生阶段：
（2）检测阶段：
（3）输出阶段：
接下来，将给出系统详细的计算过程。通过该计算过程可以看出触发型膜上带蛋白的时间膜系统在时间无关模式下是如何工作的。系统在初始状态下，膜1中含有对象no，膜2中含有对象a1。另外，膜1上含有蛋白质g，膜2上含有蛋白质p1…pn，膜3上含有蛋白质q，膜4上含有蛋白质s。系统的初始格局如图3-3所示。
图3-3 系统的初始格局
1）产生阶段
对于给定的含有n个变量和m个子句的布尔公式，设变量为xi，1≤i≤n。第一步，系统开始运行，这时规则R1，1和R12同时开始执行。规则R1，1使用分裂规则，在膜2上蛋白质p1以及膜2中对象a1的作用下，膜2分裂为两个具有相同膜标签的新膜，对象a1进化为t1，1（变量x1的赋值为真）和f1，1（变量x1的赋值为假）分别处于这两个新膜中。下一步，规则R2，1，1和R3，1，1同时开始执行，这些规则对应于寻找第一个子句中变量x1的赋值（真或假）满足的子句。m个子句分别对应m条规则，每次只能执行一条规则。因此系统通过循环执行的方式依次应用R2，1，j（resp.，R3，1，j）中的规则。每执行一次规则，膜2中对象t1，j（resp.，f1，j）第二下标的值就会加1。这样，当R2，1，j（resp.，R3，1，j）中所有规则执行结束时，对象t1，j（resp.，f1，j）膜上蛋白质第二下标的值就会达到m＋1。
当R2，1，j中所有规则执行结束时，对象t1，j变为t1，m＋1。这时，开始执行规则R4，1，膜2中的对象t1，m＋1被送出膜外。当规则R4，1执行结束时，如果膜2内出现对象f1，m＋1（说明规则R3，1，j对应的所有规则已经执行结束），规则R5，1开始执行，对象t1，m＋1被送入膜2内进化为对象c，而对象f1，m＋1被送出膜外并进化为对象b1。接着，规则R6，1开始执行，对象b1被送入膜4内。当对象b1出现在膜4中时，在膜上蛋白质s′的作用下就会执行R7，1启动分裂规则。在新生成的膜中，每个膜中都会有一份生成的对象a2。这样，在膜4膜上蛋白质和膜内对象的共同作用下，规则R8，1开始执行，每个膜4中的一个对象a2送出膜4，同时其膜上的蛋白质还原为s。最后，规则R9，1开始执行，每个对象a2分别进入每一个膜标签为2的膜中，为下一次分裂规则的应用做准备。
后面的计算过程类似于变量x1第一次循环计算过程（即从规则R1，1到R9，1的执行过程）。一般地，每个变量对应的细胞持续不断地分裂，寻找使所有当前变量赋值满足的所有子句，直至所有变量对应的循环计算过程执行结束。一般来说，对于变量xi的第i次循环计算过程（1≤i≤n），就规则的执行时间而言，由于系统是在时间无关模式下工作的，规则R2，i，j和R3，i，j可能在不同的RS步内执行结束，所以t1，m＋1和f1，m＋1并不是同时生成的。当t1，m＋1和f1，m＋1分别出现在膜2外和膜2内，说明前面所有的规则已经执行结束，这样规则R5，i就具有规则同步功能。这里需要说明的是，规则R5，i的执行可能对应到多个膜2，但它们是同时开始执行的，而且也是同时执行结束的，因此这个过程只需要1个RS步。对于规则R6，i，这里需要注意的是，在产生阶段每次变量循环计算过程中对象bi的数量和具有膜标签为4的膜的数量是相等的，并且在膜上蛋白质s的精确控制下可以确保任何一个膜4中都有且仅有一份对象bi进入该膜内。然后通过规则R7，i使用分裂规则可以使膜4的数量翻倍，同时对象bi变为ai＋1后的数量也翻倍。最后，规则R9，i可以确保任何一个膜2中都有且仅有一份对象ai进入膜内。需要注意的是，整个计算过程都是在时间无关模式下完成的，并且由于使用的是触发型膜上带蛋白膜系统，膜上的任何蛋白质仅有两个状态。
总的来说，系统经过2mn＋6n个RS步后，产生阶段将执行结束。此时，在膜1中分别产生2n个膜标签为2和4的膜（见图3-4）。
图3-4 产生阶段结束后的膜结构
2）检测阶段
当对象an＋1出现在膜标签为2的膜内时，说明产生阶段的所有规则已经执行结束。此时如果膜3中存在对象r1，则通过使用规则R10，对象an＋1进入膜3并进化为对象c，膜3中的对象r1送出膜外并进化为对象s2。最后通过使用规则R11，i检查膜3中是否存在对象r2、r3、……、rm。最终，如果一个膜2中出现对象sm＋1，则说明这个膜中所有变量的赋值对应着SAT问题的一个可满足解。总的来说，整个检测阶段最多需要m个RS步。
3）输出阶段
当检测阶段结束时，将会有以下两种情况。
（1）肯定的答案：公式是可满足的。在这种情况下，至少有一个膜标签为2的膜中出现对象sm＋1，因此可以应用规则R13。通过使用该规则，对象sm＋1进化为物质yes，同时把它被送出膜2外，然后使用规则R14把物质yes送出膜1外，同时膜1上的蛋白质从g′变为g。当规则R12和R14都执行结束时，通过使用规则R15，在膜1上蛋白质g的作用下，物质no重新进入膜1。此时，系统计算停止，只有物质yes保留在环境中，说明至少存在一个可满足解。总的来说，输出阶段最多需要3个RS步，这个结果独立于规则的任何时间映射e。
（2）否定的答案：公式是不满足的。在这种情况下，当检测阶段执行结束，没有任何一个膜标签为2的膜中出现对象sm＋1。因此，规则R13、R14和R15将不会执行。最终，当系统停止时，对象no仍然在环境中，由此可以得出该SAT问题没有可满足解的结论。在这种情况下，该过程不需要RS步。
系统计算效率的理论分析
构造
的统一算法必需资源表示如下：
（1）膜内对象集合O的数量：5mn＋4n＋2m＋4；
（2）膜上蛋白质集合P的数量：2n＋5；
（3）初始物质的数量：2；
（4）膜上初始蛋白质的数量：n＋3；
（5）初始膜的数量：4；
（6）规则总数：2mn＋7n＋m＋4；
（7）规则最大长度：6。
同样，对于触发型时间膜上带蛋白膜系统
同样是时间无关充分的和时间无关完备的。
如果公式γ是可满足的，则在最多2mn＋6n＋m＋3个RS步后，P系统将停止工作；如果公式γ是不满足的，则在最多2mn＋6n＋m－1个RS步之后，P系统将停止工作。对于这两种情况，产生阶段的RS步最多均为2mn＋6n个RS步；对于检测阶段，前者需要m个RS步，后者最多需要m－1个RS步（因为检测阶段的m条规则不可能全部执行）；而对于输出阶段，前者需要3个RS步，后者不需要RS步。显然，系统的整个计算是时间无关多项式有界的。
受到生物实际启发，本节使用触发型膜上带蛋白的时间膜系统在时间无关模式下求解了SAT问题。该模型即使在膜上的每一类蛋白质仅有两种可达状态的情况下，依然可以对SAT问题进行求解。证明了该模型在时间无关模式下求解NP完全问题的有效性。
定理3.4：SAT∈PMCFTPPM（6）
推论3.2：NP∪co－NP⊆PMCFTPPM?（6）
显然，SAT是NP完全问题。注意到在本章的证明过程中，触发型膜上带蛋白膜系统中使用的所有进化规则的最大长度为6，而且系统在时间无关模式下工作。根据前面的定义以及证明，系统在多项式时间内给出了该问题的统一解，因此很容易得到PMCFTPPM（6）。
本章研究了基于膜上带蛋白时间膜系统的计算有效性，对现有的研究结果进行了改进。将时间无关引入触发型膜上带蛋白膜系统，并证明了SAT问题可以通过该系统以统一的方式在多项式时间内求解。其中，系统中规则的执行时间长短对计算结果没有任何影响，该研究拓宽了现有膜上带蛋白的时间膜系统的研究范围。