4.2　具有细胞分裂的类组织时间膜系统求解SAT问题

4.2　具有细胞分裂的类组织时间膜系统求解SAT问题

定理4.1：SAT问题可以通过一族基于细胞分裂的时间组织膜系统在多项式RS步内以统一的方式解决。

证明：对于具有n个布尔变量和m个子句的公式，考虑命题公式γ＝C1∧C2∧…∧Cm，其中，k≤n｝，1≤j≤m，1≤i≤是命题变量xk的否定形式。

将例子γ按如下形式编码：

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

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

其中，O为字母表：

其中，对象ti，j表示变量xi的赋值为真（true），对象fi，j表示变量xi的赋值为假（false）；对象rj表示变量赋值使得子句j是可满足的；物质yes表示公式是可满足的，而物质no表示公式是不满足的；E为环境中存在的任意多份对象：

另外，Σ＝｛Y i，j，N i，j，B i，j|1≤i≤n，1≤j≤m｝为在O内的输入字母表；w 1＝｛yes，no｝，w 2＝a 1是各个细胞内初始物质；i in＝2为输入细胞，i out＝0是保存最后计算结果的输出区域；每条规则的执行时间通过时间映射e：R→N得到，其中R是包含以下规则的规则集。

（1）产生阶段：

（2）检测阶段：

（3）输出阶段：

该算法的计算过程分为以下几个阶段：

（1）产生阶段：通过分裂规则R1，i将细胞2分裂成两个新细胞，该过程循环执行直至所有可能的候选解都在这些细胞中产生，这样就能产生指数级的计算空间。最后，将产生2n个标签为2的细胞。规则集合Rt和Rf用于检查每个子句中当前变量xi（1≤i≤n）的赋值。从R8，i到R14，i的规则主要用于为变量xi的下一次循环计算做准备；

（2）检测阶段：系统检查公式是否存在一组变量的赋值，使得布尔公式的值为真。如果存在一组变量的赋值可以满足所有子句，则说明至少有一个可满足解，即该布尔公式是可满足的；否则，该布尔公式是不满足的。利用规则R15和R16，i检测出所有变量赋值满足的子句，并产生最终的检测结果；

（3）输出阶段：通过规则R17到R19，系统根据检测阶段的结果向环境中输出yes或者no作为计算结果。

接下来，将给出系统详细的计算过程。通过该计算过程可以看出，在有输入多重集cod（γ）的情况下，使用细胞分裂的类组织膜系统在时间无关模式下是如何工作的。

1）产生阶段

设e是规则的执行时间。对于给定的含有n个变量和m个子句的布尔公式，设变量为xi，1≤i≤n。一般地，细胞2中的对象ai对应于变量xi。系统在初始状态下，细胞1中含有物质yes、no；细胞2中含有对象a1和输入多重集cod（γ）。

第一步，系统开始运行，在标签为2的细胞中对象a1的作用下，应用分裂规则R1，1将细胞2分裂为两个具有相同标签的新细胞，同时，对象a1进化为t1，1和f1，1后分别出现在新生成的细胞中。其中，对象t1，1对应于变量x1的赋值为真，对象f1，1对应于变量x1的赋值为假。在第一步，除了应用规则R1，1之外，规则R17也开始执行。在规则R1，1和R17的执行期间，没有任何其他可以执行的规则，因此这个过程仅需一个RS步。

当规则R1，1执行结束时，规则R2，1，j和R5，1，j（1≤j≤m）同时开始执行。一般地，对象ti，1和fi，1对应于检查第一个子句中变量xi的赋值为真或假是否可满足。通过应用规则R2，1，j和R5，1，j中的第一条规则，如果细胞2中的对象t1，j和对象Y1，j（或者对象f1，j和对象N1，j）同时出现，那么规则R2，1，j和R 5，1，j（1≤j≤m）将被应用，多重集t 1，j Y 1，j（或者f 1，j N 1，j）被送出该细胞进入环境，同时环境中的对象b i，j进入细胞2。当规则R 2，1，j和R 5，1，j中的第一条规则执行结束，可以应用该规则中对应的第二条规则。通过使用该规则，细胞2中的对象b i，j被发送出细胞2，同时环境中的对象r j进入细胞2，生成的对象r j表示变量的赋值对应的子句是可满足的。如果细胞2中存在的是对象t 1，j（或者f 1，j）和其他对象，则不会产生对象r j，说明当前变量赋值对应的该子句是不满足的。m个子句分别对应m条规则，每次只能执行一条规则。因此通过循环的方式依次执行R 2，i，j、R 3，i，j和R 4，i，j（resp.、R 5，i，j、R 6，i，j和R 7，i，j）中的规则。每执行一次规则，对象t 1，j或者f 1，j的下标j值就会加1。这样，对于产生阶段每次循环计算过程，R t（resp.，R f）中的所有规则执行结束时，对象t 1，j（resp.，f 1，j）的下标j值就会达到m＋1，即生成t 1，m＋1（resp.，f 1，m＋1）。当规则R 1，i执行结束后，规则R t（R 2，i，j，R 3，i，j，R 4，i，j）与R f（R 5，i，j，R 6，i，j，R 7，i，j）这两大类规则集合中各有一条规则是同时开始执行的，因此这两条同时开始执行的规则仅需一个RS步。此外，考虑规则R t和R f中的最大规则数目，即R 2，i，j和R 5，i，j。对于变量的每次循环计算过程，注意到在当前变量的某个子句中这两个规则不可能都同时执行（因为同一子句中的同一个变量只能是x i或者）。因此，整个过程最多需要3m－1个RS步。

图4-1展示了n个变量的循环计算过程，上述规则产生的对象可以用二叉树中的结点表示。公式中每个变量在每次循环中相应的细胞都会分裂为两个细胞，这两个细胞中分别产生对象t i，m＋1和f i，m＋1对应二叉树的结点。因此每个结点对应变量的赋值true或false（左子树对应true，右子树对应false）。对于变量x i的每次循环计算过程，当规则R t（resp.，R f）中对应的规则全部执行结束时，在每个细胞2中会生成对象t i，m＋1（resp.，f 1，m＋1）。由于系统在时间无关模式下工作，对象t i，m＋1和f 1，m＋1并不是同时生成的。另外需要注意的是，对于每一次循环中每个包含对象t i，m＋1（resp.，f i，m＋1）的细胞，由于其中应用的规则是相同的，因此对象t i，m＋1（resp.，f i，m＋1）在每个细胞2中是同时生成的。这样，这些规则就能并行地同时执行。例如，对于图中变量x 3的循环计算过程，四个对象t 3，m＋1（resp.，f 1，m＋1）会在细胞2中同时产生。

图4-1　变量分裂过程

根据上述分析，规则R 8，1和R 9，1可能是从不同的RS步开始执行的。当生成对象t 1，m＋1（resp.，f 1，m＋1）时，应用规则R 8，1（resp.，R 9，1），环境中的对象多重集T 1d（resp.，F 1d）进入细胞2与对象t 1，m＋1（resp.，f 1，m＋1）进行交换。规则R 8，1（resp.，R 9，1）可以确保在具有标签2的每个细胞中只生成一个对象d。当在细胞2中生成对象T 1（resp.，F 1）时，规则R 10，1（resp.，R 11，1）开始执行，通过该规则可以将对象T 1（resp.，F 1）发送到细胞1。当规则R 10，1（resp.，R 11，1）执行结束，规则R 12，1开始启动执行。此时，在细胞1中存在多重集T 1 F 1，环境中的对象e 2进入细胞2与多重集T 1 F 1交换。随后，规则R 13，1开始执行，细胞1中的对象e 2发送出细胞进入环境，同时，两份对象a 2进入细胞1。最后，应用规则R 14，1，细胞2中的对象d和细胞1中的对象a 2进行交换。

因为系统在时间无关模式下工作，显然e（R t）＋e（R 8，1）＋e（R 10，1）可能不等于e（R f）＋e（R 9，1）＋e（R 11，1）。规则R 12，1可以解决系统在运行过程中的同步问题，当该规则执行结束，说明前面所有的规则已经执行结束。

当规则R 13，1执行结束，开始应用规则R 14，1，每个细胞2将同时获得一个对象a 2。由于P系统极大并行性的原理，规则R 14，1的应用在每个细胞2中是同时完成的。此规则的执行只需要一个RS步。最终，每个细胞2中包含一个对象a 2。此时，变量x i（1≤i≤n）的第一次循环计算过程（即从规则R 1，1到R 14，2的执行过程）执行结束，生成的对象a 2用于变量在下一次循环中使用细胞分裂规则。当规则R 14，1执行结束时，总的来说，该过程总共最多需要3m＋7个RS步。

变量x i的第一次循环执行计算过程结束，每个细胞2中包含一个对象a 2。在对象a 2的影响下，在每个细胞2中同时执行规则R 1，2。通过应用细胞分裂规则，生成标签为2的四个细胞。类似地，该系统以循环的方式执行上述过程，所有变量将被赋值并找出满足的子句，直到所有变量的循环计算过程执行结束。

从R 1，1到R 14，n的可用规则按以下顺序执行。

第一次循环计算过程中规则的执行：

｛R 1，1｝→｛｛｛R 2，1，j，R 3，1，j，R 4，1，j｝→｛R 8，1｝→｛R 10，1｝｝（resp.，｛R 5，1，j，R 6，1，j，R 7，1，j｝→｛R 9，1｝→｛R 11，1｝）｝→｛R 12，1｝→｛R 13，1｝→｛R 14，1｝

第二次循环计算过程中规则的执行：

｛R 1，2｝→｛｛｛R 2，2，j，R 3，2，j，R 4，2，j｝→｛R 8，2｝→｛R 10，2｝｝（resp.，｛R 5，2，j，R 6，2，j，R 7，2，j｝→｛R 9，2｝→｛R 11，2｝）｝→｛R 12，2｝→｛R 13，2｝→｛R 14，2｝

……

最后一次循环计算过程中规则的执行：

｛R 1，n｝→｛｛｛R 2，n，j，R 3，n，j，R 4，n，j｝→｛R 8，n｝→｛R 10，n｝｝（resp.，｛R 5，n，j，R 6，n，j，R 7，n，j｝→｛R 9，n｝→｛R 11，n｝）｝→｛R 12，n｝→｛R 13，n｝→｛R 14，n｝

总的来说，系统经过3mn＋7n个RS步后，产生阶段将结束执行。此时，生成2n个标签为2的细胞。

2）检测阶段

当对象a n＋1出现在标签为2的细胞中时，说明产生阶段所有规则已经结束执行。注意到每个细胞中应用规则R 14，n时遵循极大并行性的原理，因此，每个细胞2中的对象a n＋1将同时出现。当产生阶段结束执行，每个细胞2中存在着集合｛r 1，r 2，…，r m｝中的一些对象（或不存在这些对象）。这些对象表示相应的子句在对应的变量赋值下是可满足的。当细胞2中出现对象a n＋1和对象r 1（如果该对象存在），通过使用规则R 15，对象r 1和对象a n＋1进入环境，同时对象s 2进入细胞2。如果对象s i（2≤i≤m）出现在细胞2中，则可以应用规则R 16，j。当对象s m出现在细胞2中时，可以应用规则R 16，m。这样，就可以在细胞2中产生对象s m＋1。需要注意的是，整个过程规则以时间无关的模式执行。总的来说，整个检测阶段最多需要m个RS步。

3）输出阶段

当检测阶段以及规则R 17执行结束时，将会有以下两种情况：

（1）肯定的答案：公式是可满足的。在这种情况下，在标签为2的细胞中生成对象s m＋1，因此可以应用规则R 18。通过使用这个规则，细胞2中的对象s m＋1和细胞1中的物质yes相互交换。这样，细胞2中就出现了物质yes。接下来，规则R 19开始执行，物质yes被送出细胞2进入环境，而环境中存在的一份物质no进入细胞2。因此，当P系统停止工作时，yes将出现在环境中。由此可以得出一个结论，即至少有一个可满足解。总的来说，输出阶段最多需要2个RS步，这个结果独立于规则的任何时间映射e。

（2）否定的答案：公式是不满足的。在这种情况下，对象s m＋1不会出现在任何一个标签为2的细胞中。因此，规则R 18和R 19都不会执行。最终，当系统停止时，对象no仍然在环境中，由此可以得出没有可满足的解的结论。在这种情况下，该过程不需要RS步。

下面给出一个实例来说明ΠSAT（m，n）是如何工作的，具体的SAT问题的例子使用的公式为：。

ΠSAT（m，n）的初始格局如图4-2所示。第一步，在标签为2的细胞中对象a 1作用下分裂为两个具有相同标签的新细胞；同时，对象a 1进化为t 1，1和f 1，1后分别出现在新生成的细胞中。第一步除了应用规则R 1，1之外，规则R 17也开始执行。

图4-2　初始格局

当规则R 1，1结束执行，规则R 2，1，j和R 5，1，j（1≤i≤m）同时开始执行。通过循环的方式依次执行R 2，1，j，R 3，1，j和R 4，1，j（resp.，R 5，1，j，R 6，1，j和R 7，1，j）中的规则。每执行一次规则，对象t 1，j或者f 1，j的下标j值就会加1，最终生成t 1，m＋1（resp.，f 1，m＋1）。然后，应用规则R 8，1（resp.，R 9，1），环境中的多重集T 1d（resp.，F 1d）进入细胞2与对象t 1，m＋1（resp.，f 1，m＋1）进行交换。当在细胞2中生成对象T 1（resp.，F 1），规则R 10，1（resp.，R 11，1）开始执行，通过它可以将对象T 1（resp.，F 1）发送到细胞1。当规则R 10，1和R 11，1都结束执行时，可以得到系统此时的格局（见图4-3）。此时，不能确定规则R 17是否已经完成执行，因为系统在时间无关模式下运行，其中规则的执行时间长短可能是任意的。为了方便描述，在图4-3到图4-8中假设规则R 17已经结束执行。需要注意的是，在图4-4到图4-8的膜结构图中，有些物质对计算过程以及最后计算结果不会有影响，因此并没有将它们表示在图中。

图4-3　规则R10，1和R11，1执行结束后

接着，规则R 12，1、R 13，1和R 14，1执行结束后，可以得到系统此时的格局（参见图4-4）。当变量x i（1≤i≤n）的第一次循环计算过程执行结束，标签为2的细胞中有对象a 2。在对象a 2的影响下，规则R 1，2将被应用，生成标签为2的四个细胞。当变量的第二次循环计算过程中所有规则应用完成时，即当规则R 14，3的执行结束，可以得到系统此时的格局（参见图4-5）。类似地，变量的第三次循环计算过程中所有规则应用完成时，可以得到系统此时的格局（参见图4-6）。

图4-4　变量的第一次循环执行结束后

图4-5　变量的第二次循环执行结束后

图4-6　变量的第三次循环执行结束后

当在标签为2的细胞中产生对象a 4时，通过使用规则R 15，对象s 2进入细胞2。最后，可以生成对象s 4（见图4-7）。当对象s 4存在标签为2的细胞中时，应用规则R 18，对象s 4与细胞1中的对象yes交换。最终，通过应用规则R 19，对象yes被发送到环境，同时环境中的对象no进入细胞2中。此时，系统停止工作。在环境中出现对象yes，说明该公式是可满足的（见图4-8）。

图4-7　检测阶段结束后

图4-8　系统最终格局