3.2　膜上带蛋白的时间膜系统求解SAT问题

3.2　膜上带蛋白的时间膜系统求解SAT问题

定理3.1：SAT问题可以通过一族膜上带蛋白的时间膜系统使用a、c、d，以及f类规则在多项式RS步内通过基本膜分裂以统一的方式解决。

证明：对于具有n个布尔变量和m个子句的公式，本章考虑命题公式γ＝C 1∧C 2∧…∧Cm，其中，C j＝y j，1∨…∨y j，pj，y j，i∈≤k≤n｝，1≤j≤m，1≤i≤是命题变量x k的否定形式。考虑多项式时间计算函数为g（n，k）＝（（n＋k）（n＋k＋1）／2）＋n。

再通过以下多重集对γ进行编码，其中1≤j≤m，1≤i≤n。

接下来，在时间无关模式下定义一族膜上带蛋白的识别P系统，该系统可以处理提供输入多重集cod（γ）的所有例子γ。对于给定的含有n个变量和m个子句的布尔公式，该识别P系统构造如下：

其中，O为字母表：

对象r j表示变量赋值使得子句j是可满足的，物质yes表示公式是可满足的，而物质no表示公式是不满足的。

P为蛋白质对象集：

蛋白质对象表示变量xi的赋值为真（true），蛋白质对象表示变量xi的赋值为假（false）。

另外，Σ＝｛Yi，j，Ni，j，Bi，j|1≤i≤n，1≤j≤m｝为在O内的输入字母表；μ＝［［］2［］3］1为初始膜结构；w1＝no，w2＝a1，w3＝λ是各个膜内的初始物质；z1＝q0，z2＝p1，z3＝y1是各个膜上初始状态下的蛋白质对象；iin＝2为输入膜，iout＝0是保存最后计算结果的输出区域；R1，…，R3表示区域1、2、3中规则的有限集，包含以下三个阶段的规则。

（1）产生阶段：

接下来，将给出系统详细的计算过程。通过计算过程可以看出该系统是如何工作的。设e是规则的执行时间。对于给定的含有n个变量和m个子句的布尔公式，设变量为xi，1≤i≤n。系统在初始状态下，膜1中含有对象no；膜2中含有对象a1，该对象对应于变量x1。另外，膜1上含有蛋白质q0；膜2上含有蛋白质p1；膜3上含有蛋白质y1。系统的初始格局如图3-1。

图3-1　系统的初始格局

1）产生阶段

一般地，膜标签为2的膜中对象ai对应于变量xi，1≤i≤n。第一步，系统开始运行，这时规则R1，1和R11同时开始执行。规则R1，1使用分裂规则，即在膜2上蛋白质p1的作用下，膜2分裂为两个具有相同膜标签的新膜。该膜分裂规则仅仅受到膜上蛋白质的控制，而不需要膜内物质的作用。同时，膜2上蛋白质p1进化为和后分别出现在新生成的膜上。其中，蛋白质对应于变量x1的赋值为真，蛋白质对应于变量x1的赋值为假。在该过程中，除了规则R1，1和R11之外，没有任何可以执行的规则，因此仅需一个RS步。当规则R1，1执行结束时，规则R2，1，1和R3，1，1同时开始执行。这些规则对应于寻找第一个子句中变量x1的赋值（真或假）满足的子句。应用规则R2，1，1（resp.，R3，1，1），如果膜内的输入多重集中存在对象Yi，j（resp.，Ni，j），膜内会生成对象rj，说明子句j中对于变量x1的赋值是可满足的；其他情况生成对象c。m个子句分别对应m条规则，每次只能执行一条规则。因此该过程循环执行R2，1，j（resp.，R3，1，j）中的规则。每执行一次规则，膜上蛋白质第二个下标的值就会加1。这样，当R2，1，j（resp.，R3，1，j）中所有规则执行结束时，膜上蛋白质第二个下标的值就会达到m＋1。最终，在每个膜2中将生成来自集合｛r1，r2，…，rm｝中的一些对象（或没有任何对象）。

当R2，1，j中的所有规则执行结束时，对应膜上的蛋白质为。这时，开始执行规则R4，1，膜上蛋白质改变为，同时对象a1被送出膜2。当规则R4，1执行结束时，对象a1出现在膜1中。这时，如果R3，1，j中的规则尚未执行结束，则后面的规则不能执行。当R3，1，j中的所有规则以及规则R4，1执行完毕，规则R5，1开始执行，对象a1进化为b1。同时，该膜对应的膜上蛋白质也改变为。当对象b1出现在膜1中，说明前面所有的规则已经执行结束。这时，应用规则R6，1，膜3上的蛋白质y1改变为，同时对象b1进入膜3中并进化为a2。当膜3上出现蛋白质，在该蛋白质的作用下就会执行R7，1启动分裂规则。这样，在新生成的膜中，每个膜上的蛋白质都会变为y2，而每个膜中都会有一份对象a2。因此，在膜3膜上蛋白质和膜内对象的共同作用下，规则R8，1开始执行，每个膜3中的一个对象a2被送出膜3。最后，规则R9，1开始执行，每个对象a2分别进入每一个膜标签为2的膜中，同时把这些膜上的蛋白质变为p2，为下一次分裂规则的应用，进入下一次循环计算过程做准备。

通过以上计算过程的分析可以看出，当变量xi的第一次循环计算执行结束时，每个具有膜标签为2的膜上蛋白质都为p2，膜2内都有一个对象a2。在膜上蛋白质p2的作用下，规则R1，2在每个膜2中同时开始执行并产生4个具有相同膜标签为2的新膜。以下用“当前变量”表示每次变量循环计算过程中正在执行的变量，其值对应着取值范围1≤i≤n中的某个值。后面的计算过程类似于变量x1第一次循环计算过程（即从规则R1，1到R9，1的执行过程）：系统继续为变量x2赋值（真和假），可以获得当前变量赋值满足的所有子句。当变量xi的第二次循环执行结束，系统继续为其余变量赋值。类似地，每个变量持续不断地分裂，寻找满足当前变量赋值的所有子句。其中，对于规则R2，1，j和R3，1，j，寻找变量赋值是否满足子句的计算过程最多需要2m－1个RS步（规则R2，1，j和R3，1，j中的第一个规则同时开始执行）。当变量xi（1≤i≤n）的第二次循环执行结束，系统继续为变量x3，…，xn赋值（真和假）。类似地，对于变量xi的每次循环计算过程，寻找满足当前变量赋值的所有子句。由于系统在时间无关模式下工作，规则R2，i，j和R3，i，j可能在不同的RS步内执行结束，因此规则R4，i和R5，i起到解决规则同步问题的作用。这样，当对象bi出现在膜1中时，说明之前所有规则已经执行结束。这里需要注意的是，对于变量xi的每次循环计算过程，对象bi的数量和膜标签为3的膜的数量是相等的。因此，规则R6，i可以确保任何一个膜3中有且仅有一份对象bi进入膜内并进化为ai＋1。通过规则R7，i使用分裂规则可以使膜3的数量实现翻倍。可以看出，此时对象ai＋1的数量总是与膜标签为2的膜的数量是相等的。因此，规则R9，i可以确保任何一个膜1中都有且仅有一份对象ai进入膜2内。此外，由于P系统的极大并行性原理，对于膜标签为2的膜，规则R9，i同时开始执行并同时结束执行。应该指出的是，该系统以循环的方式执行上述过程，所有变量将被赋值并找出满足的子句，直到所有变量的循环计算过程执行结束。

总的来说，系统经过2mn＋6n个RS步后，产生阶段执行结束。此时，在膜1中分别产生2n个膜标签为2和3的膜（见图3-2）。

图32　产生阶段结束后的膜结构

2）检测阶段

当产生阶段结束时，每个膜标签为2的膜中存在着集合｛r1，r2，…，rm｝中的一些对象（或不存在这些对象）。这些对象表示相应的子句在对应变量赋值下是可满足的。如果膜2中存在对象r1，在该膜上蛋白质pn＋1的作用下，通过使用规则R10，1，膜上蛋白质pn＋1变为pn＋2，对象r1保持不变。如果生成了pn＋2，则说明该膜中存在对象r1。如果膜上生成了蛋白质pn＋2，通过使用规则R10，2检查膜中是否存在对象r2。就这样，系统检测膜中是否存在对象r3，r4，…，rm。最后，如果一个膜2上出现蛋白质pn＋m＋1，则说明这个膜中所有变量的赋值对应着SAT问题的一个可满足解。

3）输出阶段

当检测阶段结束，将出现以下两种情况之一。

（1）肯定的答案：公式是可满足的。在这种情况下，至少有一个膜标签为2的膜上出现蛋白质pn＋m＋1，因此可以应用规则R12。通过使用这个规则，在膜2上蛋白质pn＋m＋1的作用下，对象an＋1进化为物质yes，同时被送出膜2外。当规则R11和R12都执行结束时，通过使用规则R13，物质yes被送出膜1，并将该膜上的蛋白质从q1变为q2。最后，在膜1上蛋白质q2的作用下，物质no重新进入膜1。此时，系统计算停止，只有物质yes保留在环境中，说明至少存在一个可满足解。总的来说，输出阶段最多需要3个RS步，这个结果独立于规则的任何时间映射e。

（2）否定的答案：公式是不满足的。在这种情况下，当检测阶段执行结束，没有任何一个膜标签为2的膜上出现蛋白质pn＋m＋1。因此，规则R12、R13和R14将不会执行。最终，当系统停止时，对象no仍然在环境中，则该SAT问题没有可满足解。在这种情况下，该过程不需要RS步。

系统计算效率的理论分析如下。

对于具有n个变量和m个子句的SAT问题，构造统一算法必需资源可表示如下：

（1）膜内对象集合O的数量：3mn＋2n＋m＋4；

（2）膜上蛋白质集合P的数量：2mn＋5n＋m＋5；

（3）初始物质的数量：2；

（4）膜上初始蛋白质的数量：3；

（5）初始膜的数量：3；

（6）规则总数：2mn＋6n＋m＋4；

（7）规则最大长度：4。

对于膜上带蛋白的识别P系统在统一方式下求解SAT问题，对任意的时间映射e：R→N，系统将在确定的RS步后停止计算。最终，对象yes或no必然会在可行的时间内出现在环境中。因此，系统是时间无关充分的和时间无关完备的。

如果公式γ是可满足的，则在最多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问题可以通过一族膜上带蛋白的识别P系统在多项式RS步内解决。系统以极大并行的方式运行，并且膜上的蛋白质可以实现精确地控制规则的应用。因此，所构造的P系统在计算过程中有其自身的优势。

定理3.2：SAT∈PMCTPPM（4）

推论3.1：NP∪co－NP⊆PMCTPPM（4）

显而易见，SAT是NP完全问题。注意到在本小节的证明过程中，系统使用的进化规则的最大长度为4。系统在时间无关模式下工作，根据前面的定义以及证明，系统在多项式时间内给出了该问题的统一解，因此很容易得到PMCTPPM（4）。

文献［5］证明了通过一族膜上带蛋白的时间膜系统使用非基本膜分裂求解了SAT问题，系统中进化规则的最大长度为6。而本章使用基本膜分裂而没有使用非基本膜分裂，且系统中进化规则的最大长度从6减少为4，从而改进了文献［5］中的研究结果。