5.3 HTP-OE的计算能力以及计算效率
在本小节，将对基于对象进化规则的内稳态类组织膜系统的计算能力和计算效率进行研究。具体地，使用注册机对该系统产生数的通用性进行证明；另外，还将给出该系统在时间无关模式下的SAT问题统一解。
5.3.1 HTP-OE的通用性证明
下面对HTP-OE系统的计算能力进行研究。具体地，将该模型与经典的图灵机计算模型进行比较，分别在标准时间和时间无关模式下对该模型产生数的能力进行研究。
定理5.4：NOP2，3（（a），（b））HTP-OE＝NRE
证明：下面通过模拟注册机证明HTP-OE系统的通用性，其中仅针对标准膜系统下HTP-OE系统的规则类型a和b。NOP m，n表示系统产生的自然数集合（m表示初始细胞的数量，n表示系统中的最大规则长度）。设有通用的带m个注册器的注册机M＝（m，H，l 0，l h，I），产生的数存储在注册器1中。另外，假定注册器1中没有加法指令，并且当计算结束时，除注册器1外，其他注册器均为空。系统构造如下：
其中：O＝｛a r|1≤r≤m｝∪｛l，l′，l（2），l（3），l（4），l（5），l（6）|l∈H｝；w 1＝λ；w 2＝｛l（4）|l∈H｝；i out＝1。
下面将构造规则集合R。
（1）对于每条加法指令l i：（ADD（r），l j，l k），指令集合构造如下。
在某个时刻，系统通过使用规则R 1开始运行ADD指令l i。然后下一计算步，规则R 2或R 3非确定性地执行其中一条，使得注册器r的值增加1，从而满足了ADD指令的要求。同时，对象l j或l k会随机产生，因此可以模拟下一条指令。
（2）对于每条减法指令l i：（SUB（r），l j，l k），指令集合I构造如下。
在某个时刻，系统通过使用规则R 4开始运行SUB指令l i。下一计算步，执行规则R 5生成多重集
。在这个时刻，会出现以下两种可能性：
（1）第一种情况，至少有一个对象a r存在细胞1中，显然规则R 6和规则R 7会同时开始执行，这样多重集
会出现在细胞1内，下一个计算步，规则R 8开始执行，从而产生对象l j；同时，执行规则R 10消耗掉
并产生对象
。最后，使用规则R 11，对象
进入细胞2使得至少一份这种对象可以在下一次模拟中使用。
（2）第二种情况，没有对象a r存在细胞1中，显然规则R 6不会执行，而是仅仅执行规则R 7。下一个计算步，规则R 9和R 10开始执行，使得多重集
进化为l k，说明系统已经准备好了开始模拟指令l k。最后，执行规则R 11，对象
进入细胞2。
模拟以上SUB指令两种情况的执行过程如表5-1和表5-2所示。其中，在每个计算步中，细胞1和细胞2中的对象已经列出，但并不是所有的对象都列出来（例如对象a r）。
表5-1 如果对象ar存在（标准时间下）
（续 表）
表5-2 如果对象ar不存在（标准时间下）
因此，ADD指令和SUB指令都可以正确地模拟。最终，系统停止计算，此时对象l h会出现在细胞1中。
定理5.5：
（（a），（b））HTPOE＝NRE，其中，
表示系统产生的自然数集合（m表示初始细胞的数量，n表示系统中的最大规则长度，而f表示系统在时间无关模式下工作）。
证明：与定理5.4不同的是，系统在时间无关模式下工作，在该模式下系统构造如下：
其中：O＝｛a r|1≤r≤m｝∪｛l，l′，l（2），l（3），l（4），l（5），l（6），l（7），l（8）|l∈H｝；w 1＝λ；w 2＝｛l（8）|l∈H｝；e表示规则的执行时间；i out＝1。
下面将构造规则集合R。
（1）对于每条加法指令l i：（ADD（r），l j，l k），指令集合构造如下：
以上规则与定理5.5中的ADD指令相同，这里不再对它们进行描述。
（2）对于每条减法指令l i：（SUB（r），l j，l k），指令集合I构造如下。
在某个时刻，系统通过使用规则R 4和R 5开始模拟SUB指令，会生成多重集
。当规则R 5结束执行，在产生的对象
的作用下规则R开始执 6行。接下来，规则R 7运行并在细胞2中产生多重集
，同时在细胞1中产生
。这个时刻，会出现以下两种可能性：
（1）第一种情况，至少有一个对象a r存在细胞1中，显然规则R 8和规则R 9会同时开始执行，这样多重集
会出现在细胞1内，下一个计算步，规则R 10开始执行，从而产生对象l j；同时，执行规则R 12和R 13，对象
会最终出现在细胞2中，这样为下一次模拟做好了准备。
（2）第二种情况，没有对象a r存在细胞1中，显然规则R 8不会执行，而是仅仅执行规则R 9。下一个计算步，规则R 11和R 12同时开始执行，从而产生对象l k，说明系统已经准备好了开始模拟指令l k。最后，对象
出现在细胞2中，为下一次模拟做好了准备。
在时间无关模式下模拟以上SUB指令的两种情况执行过程如表5-3和表5-4所示。其中，并不是所有的对象都列出来（例如对象a r）。
表5-3 如果对象ar存在（时间无关模式下）
表5-4 如果对象ar不存在（时间无关模式下）
因此，ADD指令和SUB指令都可以正确地模拟。最终，系统停止计算，此时对象l h会出现在细胞1中。
5.3.2 基于HTP-OE系统求解三着色问题和SAT问题
在本小节，将基于定义5.2的模型，分别对三着色问题和SAT问题进行求解。
定义5.4：三着色问题可表述如下：对于一个无向图G＝（V，E），每个顶点用｛R，G，B｝来表示颜色。其中R，G和B分别代表红色、绿色和蓝色。用函数f（x）表示图中顶点x的颜色，如果对所有的边｛u，v｝∈E都有f（u）≠f（v），则该图是可三着色的。否则，若图中不存在一个有效的三着色，则该图是不可三着色的。
根据三着色问题的一个给定算例（具有n个顶点、m条边的无向图）构造一个识别内稳态类组织膜系统，在计算的最后一步，如果该图是可三着色的，那么物质yes出现在环境中；否则物质no出现在环境中。
定理5.6：三着色问题可以在线性RS步内通过一族识别HTP-OE系统得到统一解。
证明：考虑一个包含n个顶点m条边的无向图γ＝（V，E），其中，V＝｛v 1，…，v n｝表示该无向图中的顶点，｛v i，v j｝∈E表示图中的边。
接下来，首先定义一族内稳态组织膜系统。只要向该系统提供适当的输入多重集，系统就可以处理所有的具有n个顶点m条边的所有无向图的例子。构造的系统如下：
其中，O为字母表：
其中，对象R i表示顶点为红色，对象G i表示顶点为绿色，对象B i表示顶点为蓝色；物质yes表示图中存在一个有效的三着色，而物质no表示图中不存在一个有效的三着色。另外，Σ＝｛D i，j|D i，j∈E，1≤i≤j≤n｝为在O内的输入字母表，其中共有m条边；w 1＝yes，w 2＝｛A 1，no｝；i in＝2是输入细胞；i out＝1是输出区域，保存最后的计算结果；R是下面的规则集合。
接下来，将给出系统详细的计算过程。通过该计算过程可以看出，在有输入多重集的情况下，内稳态类组织膜系统是如何工作的。
系统开始计算之前，初始配置中细胞1中含有对象yes；细胞2中含有多重集A 1，no和输入多重集。
对于给定的具有n个顶点m条边的无向图，设第i个顶点用变量x i表示，1≤i≤n。第一步，系统开始运行，在细胞2中对象A 1的作用下，应用分裂规则R 1，1将细胞2分裂为两个具有相同标签的新细胞，并在这两个细胞中产生新的对象R 1和T 1。在下一个计算步，规则R 2，1和R 3，1同时开始执行。通过这种方式，分裂规则重新执行，在产生的对象中，R 1、G 1和B 1对应着给定的无向图中第一个顶点三种可能的着色。在第三个计算步，规则R 4，1、R 5，1和R 6，1同时开始执行产生对象A 2。这样，经过三个计算步以后，对象A 2就会出现在每个标签为2的细胞中。因此，在接下来的计算步，系统会执行规则R 1，2，它对应着顶点的下一个循环执行过程。就这样，系统以循环的方式执行以上计算过程，直到所有的顶点对应的计算过程全部执行为止。总的来讲，经过3n个计算步以后，产生阶段结束，将会产生3n个细胞，在每个细胞中会出现对象A n＋1。
当对象A n＋1出现在细胞2中时，产生阶段结束，然后系统进入了检测阶段。对象D i，j（1≤i≤j≤n）对应着m条边。规则R 7，i，j用于检查顶点v i和v j是否都为红色（规则R 8，i，j和R 9，i，j分别用于检查这两个顶点的着色是否都为绿色和蓝色）。如果图中一条边上的两个顶点具有相同的颜色（例如同为红色、绿色或者蓝色），那么仅有规则R 7，i，j、R 8，i，j和R 9，i，j中的一条规则会被执行，对象A n＋1会被送到细胞1中。在下一个计算步，如果有3n份对象A n＋1在细胞1中，那么意味着计算结果是否定的答案，即在每一个细胞2中不存在一个有效三着色。在这种情况下，规则R 10将会被执行，对象no会出现在细胞1中，这时系统停止计算。因此，我们可以得出一个结论，该图的计算结果是否定的答案；相反，如果3n份对象A n＋1没有出现在细胞1中，在这种情况下，对象yes保留在细胞1中，就表明这个无向图至少具有一个三着色解。我们可以得出计算结果是肯定的答案，即图中存在一个有效的三着色。
对于具有n个顶点和m条边的三着色问题，构造Π3-COL（m，n）的统一算法必要资源可以表示如下。
（1）物质的数量：m＋12n＋3；
（2）初始细胞的数量：2；
（3）初始物质的数量：3；
（4）规则总数：3m＋6n＋1。
最终，系统将在确定的计算步后停止计算，对象yes或no必然会在可行的时间内出现在环境中。因此，系统Π3-COL（m，n）是时间无关充分的和时间无关完备的。如果图中存在一个有效三着色，则在最多3n个计算步后，P系统将停止工作；如果图中不存在一个有效三着色，则在最多3n＋1个计算步之后，P系统将停止工作。显然，系统的整个计算是线性有界的，三着色问题可以通过一族定义5.2的模型，使用规则类型a、b和c在线性计算步内解决。
下面使用定义5.2的模型，构造一族基于对象进化规则识别的内稳态类组织膜系统在时间无关模式下求解SAT问题，并给出具体的证明过程以及通过一个例子阐述该系统的工作过程。
定理5.7：SAT问题可以通过一族HTP-OE系统在多项式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≤p j，
是命题变量x k的否定形式。
将例子γ按如下形式编码：
再通过以下多重集对γ进行编码，其中1≤j≤m，1≤i≤n。
接下来，在时间无关模式下定义一族识别类组织膜系统。
其中，O为字母表：
另外，Σ＝｛Y i，j，N i，j，B i，j|1≤i≤n，1≤j≤m｝；w 1＝no，w 2＝a 1是各个细胞内初始物质；i in＝2为输入细胞，i out＝1是输出区域；每条规则的执行时间通过时间映射e：R→N得到；R是包含以下规则的规则集。
（1）产生阶段：
（2）检测阶段：
（3）输出阶段：
1）产生阶段
系统在初始状态下，细胞1中包含对象no，细胞2中为对象a 1和输入多重集cod（γ）。整个计算过程由产生阶段、检测阶段以及输出阶段组成。
总的来说，对象a i对应着SAT公式中的变量x i。系统开始运行，首先执行规则R 1，1，细胞2会分裂为两个具有相同标签的新细胞，同时，对象a 1进化为t 1，1和f 1，1后分别出现在新生成的细胞中。其中，对象t 1，1对应于变量x 1的赋值为真，对象f 1，1对应于变量x 1的赋值为假。以上整个过程仅需一个RS步。当规则R 1，1执行结束时，规则R 2，1，j、R 4，1，j、R 5，1，j、R 6，1，j、R 8，1，j和R 10，1，j同时开始执行。这时，当对象t 1，1和Y 1，1（resp.，f 1，1和N 1，1）同时出现时，规则R 2，1，j（resp.，R 6，1，j）会被执行。接下来，通过使用规则R 3，1，j（resp.，R 7，1，j）就会产生新的对象r 1。对于其他情况，对象t 1，1和Y 1，1（resp.，f 1，1和N 1，1）不会同时在细胞2中出现，那么对象t 1，1（resp.，f 1，1）第二个下标的取值就会增加。就这样，一个新的来自集合｛r 1，r 2，…，r m｝中的元素就会产生。生成的对象r j表示变量的赋值使对应的子句是可满足的。类似地，系统用循环的方式执行从R 2，i，j到R 9，i，j的规则，使得对象t 1，j（resp.，f 1，j）的下标j值不断地加1。当这些规则执行结束时，对象t 1，j（resp.，f 1，j）的下标j值会达到m＋1。
当t 1，m＋1（resp.，f 1，m＋1）出现在细胞2中时，应用多重集重写规则R 10，1（resp.，R 11，1），多重集T 1 d（resp.，F 1 d）就会在该细胞中产生。然后应用规则R 12，1（resp.，R 13，1），对象T 1（resp.，F 1）会被发送到细胞1中。最后，对象T 1和F 1将出现在细胞1中，并且通过执行多重集重写规则R 14，1生成对象e 2。随后，应用规则R 15，1生成两份相同的对象a 2。这个时刻，通用执行规则R 16，2，对象a 2将出现在细胞2中。通过这种方式，产生阶段后面的计算过程将会在下一个RS步继续执行。这时，因为细胞标签号为2的细胞内有对象a 2，此时规则R 1，2会在每个标签为2的细胞中同时执行。后面的计算过程类似于变量x 1的执行过程，并以循环的方式反复执行上述过程，所有变量将被赋值并找出满足的子句，直到n个变量执行上述循环计算过程。既然建立的P系统是在时间无关模式下运行的，所有规则的执行时间是无法确定的，因此规则R 12，i、R 13，i将可能在不同的RS步结束。具体地，产生阶段中规则的执行过程如图5-5所示。
总的来说，系统经过3mn＋7n个RS步后，产生阶段将执行结束。此时，生成2n个标签为2的细胞。
图5-5 产生阶段中规则的执行过程
2）检测阶段
当对象a n＋1出现在标签为2的细胞中时，说明产生阶段所有规则已经执行结束。这个时刻，每个细胞2中存在着集合｛r 1，r 2，…，r m｝中的一些对象（或不存在这些对象）。这些对象表示相应的子句在对应的变量赋值下是可满足的。当细胞2中出现对象r 1（如果该对象存在），将会执行规则R 17。随后，执行规则R 18，j将会检查r 2，…，r m这些对象是否全部在细胞2中。最终，如果对象sm＋1出现在任何一个标签为2的细胞中，则说明该细胞中对应的变量赋值对于SAT公式来讲是可满足的，即该赋值序列对应一个可满足解。
3）输出阶段
当检测阶段完成时，如果对象s m＋1产生，说明该SAT公式具有“肯定的答案”，否则就是“否定的答案”。因此将会有以下两种情况。
（1）肯定的答案：在对象sm＋1的作用下规则R 19和R 20会被执行，使得物质yes出现在细胞1中，从而可以得出计算结果为肯定的答案。总的来讲，这个阶段最多需要2个RS步；
（2）否定的答案：在这种情况下，系统不会执行规则R 19和R 20。因此，当系统停止时，对象no一定出现在细胞1中。这种情况不需要RS步。对于以上计算过程，所需计算资源列出如下：
①物质的数量：3mn＋6n＋2m＋3；
②初始细胞的数量：2；
③初始物质的数量：2；
④规则总数：8mn＋8n＋m＋2；
⑤规则的最大长度：3。
系统停止计算时，如果物质yes在输出细胞中，则公式γ是可满足的。对于这种情况，整个计算过程中的产生阶段、检测阶段以及输出阶段分别最多需要3mn＋7n、m以及2个RS步；而如果物质no出现在输出细胞中，则公式γ是不可满足的，整个计算过程最多需要3mn＋7n＋m－1个RS步：产生阶段最多需要3mn＋7n个RS步，检测阶段最多需要m－1个RS步，输出阶段不需要RS步。
定理5.8：SAT∈
推论5.2：NP∪co－NP⊆