膜计算下的分区问题：家庭P系统的解决方案

理论计算机科学电子笔记123（2005）93-110www.elsevier.com/locate/entcs面向元胞计算的程序设计语言我是A. Gu ti'errez-Naranj o 1 M a r io J. P'erez-J塞维利亚大学计算机科学与人工智能系西班牙塞维利亚摘要最近已经提出了几种使用P系统解决困难的数值问题的方法，并且已经注意到它们的设计具有很强的相似性。在本文中，我们提出了一个新的解决方案，分配问题，通过家庭的确定性P系统的活性膜使用2-分裂。然后，我们打算表明，细胞编程语言的想法是可能的（至少对于一些相关的NP完全问题），指出一些未来的问题关键词：膜计算，复杂性类，细胞子程序，NP完全问题1介绍在[3]中，自然计算框架内引入了一种新的计算模型，称为膜计算。它从假设开始，即在活细胞的隔室结构中发生的过程可以被解释为计算。这个模型的计算设备被称为P系统。在过去的几年里，计算机科学家、生物学家、形式语言学家和复杂性理论家已经在这个领域提出了许多结果，1 电子邮件：{magutier，marper，pagecosn}@ us.es1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.04.04494 M.A. 古铁雷斯-纳兰霍等人 理论计算机科学电子笔记123（2005）93-110既确认了该领域的相关性，又用许多开放的问题和研究路线丰富了它。在本文中，我们提出了一个家庭的P系统，解决了一个数值NP-完全问题，即分区问题。这个解决方案的设计灵感来自于以前的几个其他问题的作品，主要是子集和背包问题，但也有效性和SAT。这里介绍的设计与[5]，[6]，[8]和[10]中提出的解决方案之间的相似之处将被强调，并从中提取一些结论本文的组织如下：首先，在下一节中介绍了关于识别器P系统和复杂性类的一些初步想法;然后，在第3节中，提出了划分问题的细胞解决方案，并在第4节中给出了关于推广设计的可能性的一些评论;最后，在第5节中给出了一个应用示例，并在第6节中给出了一些最后的评论。2预赛回想一下，决策问题X是一个对（IX，θX），使得IX是有限字母表上的语言（其元素称为实例），θX是IX上的全布尔函数。也就是说，问题的每个实例的答案将是TRUE（是）或TRUE（否）。 这就是我们感兴趣的原因在使用能够接收输入、处理输入并提供布尔答案的计算设备时，在我们的例子中，我们已经选择了P系统的类与输入和外部输出（特殊对象是和否将被用来实现布尔答案）。 为了获得显著的加速，我们将努力在使用活性膜的细胞模型中，因此我们可以使用膜分割来在多项式时间内获得指数工作空间。我们还施加了一些限制，例如，我们希望系统是连续的（具有相同输入的所有计算导致相同的输出），而且每个计算都必须是有限的，此外，我们希望答案在计算的最后一步传递，通过向环境发送一个特殊的对象Y es或No。2.1带有活性膜的粗略地说，一个P系统由一个细胞状的膜结构组成，在这个膜结构的隔室中放置了多组对象，这些对象按照给定的规则以同步的、非确定性的、最大限度地平行的方式进化M.A. 古铁雷斯-纳兰霍等人理论计算机科学电子笔记123（2005）9395∈CC在[4]中可以找到一个面向外行的介绍，在[11]中可以找到更多的参考书目。定义2.1一个输入的P系统是一个元组（，，i），其中：（a）是一个P系统，具有工作字母表Γ，p个膜用1标记，.，p和初始多重集M1，.，Mp与它们相关联;（b）是严格包含在Γ中的（输入）字母表，初始多集在Γ −上;(c) i是区分（输入）膜的标记。一个P系统的计算，其输入为m M（m），一个在m上的多重集，以一种自然的方式定义。唯一的新颖之处在于，（k， k，i）的初始配置必须是与之相关联的系统的初始配置，输入多重集m∈M（n）.定义2.2设（n， n，i）是一个有输入的P系统。设Γ为膜结构的工作字母表，μ为膜结构，M1，.，Mp是n的初始多重集.设m是n上的多重集。具有输入m的（m，m，i）的初始配置是（μ，M1，. ，Mim，. Mp）。在具有输入和外部输出的P系统的情况下，以类似的方式引入计算的概念，但略有不同。我们认为，不可能观察到的内部过程中，P系统，我们只能通过发送到环境中的一些特殊对象来知道计算是否停止。我们可以用下面的方法把这些思想形式化。定义2.3识别器P系统是一个具有输入（n，n，i）和外部输出的P系统，使得：(i) 工作字母表包含两个不同的元素是，否。(ii) 所有的计算都停止了。(iii) 如果是一个计算，那么某个对象YES或某个对象NO（但不是两者）必须已经被释放到环境中，并且只在计算的最后一步。我们说是一个接受-如果对象是（分别地，否）出现在与计算相关联的外部环境中，则执行计算（分别地，拒绝计算）。相应的C.这种识别系统特别适合于解决决策问题。定义2.4具有活性膜的P系统是一个元组n =（n，H，μ，M1，. 其中：(i) m≥1，是系统的初始度;96 M.A. 古铁雷斯-纳兰霍等人 理论计算机科学电子笔记123（2005）93-110HHH→ ∈ ∈{−}∈HHHHHH(ii) 字母表是符号对象的字母表;(iii) H是膜的有限标签集;(iv) μ是一种膜结构，由m层膜组成，用H元素标记（不一定是一对一的方式）;(v) M1，...，Mm是μ上的字符串，描述了放置在μ的m个区域中的对象的初始多集;(vi) R是一组有限的进化规则，具有以下形式：(a) [a→ω]α对于h∈H，α∈{+，−， 0}，a∈H，ω∈H：这是一个对象演化规则，与标记有h的膜相关联并且取决于膜的极性，但不直接涉及膜。(b) a[ ] α1→[b] α2，其中h∈H，α1，α2∈{+，−，0}，a，b∈H：一个对象从紧邻用H标记的膜外部的区域，在这个膜中产生，可能转化成另一个物体，同时，膜的极性可以改变。(c) [a] α1→b[ ] α2for h∈H，α1，α2∈{+，−，0}，a，b∈H：一个对象从标记有H的膜发出，立即到达区域，在外部，可能转化成另一个物体，同时，膜的极性可以改变。(d) [a]αB为HH，α+，，0，a，bH：用h标记的膜在与物体的反应中溶解。皮肤永远不会溶解。（e）[a]α1→[b]α2[c]α3，其中h∈H，α1，α2，α3∈{+，−，0}，a，b，c∈H：An基本膜可以分为两个膜，相同的标签，可能会改变一些对象及其极性。这些规则根据以下原则适用• 所有的规则都是平行的，并以最大的方式应用。在一个步骤中，膜的一个对象只能被一个规则（以非确定性的方式选择）使用，但是任何可以被任何形式的一个规则进化的对象都必须进化。• 如果膜溶解，其内容物（多组和内膜）在周围区域中保持自由。• 如果同时一个用h标记的膜被一个类型的规则划分，(e) 并且在这个膜中有一些对象是通过（a）型规则进化的，那么我们假设首先使用（a）型进化规则，然后产生分裂。当然，这个过程只需要一步。• 与标记为h的膜相关的规则用于所有副本M.A. 古铁雷斯-纳兰霍等人理论计算机科学电子笔记123（2005）9397是∈∈F∈这个膜。 在一个步骤中，膜可以是仅一个步骤的对象，（b）-（e）类规则我们用2-除法表示具有活性膜的P系统的识别器类2.2复杂度类PMCF第一个关于NP完全问题在多项式时间（甚至是线性）内的“可解性”的结果因此，这些结果的构造性证明需要为问题的每个实例设计一个系统如果我们想在实验室中执行这样的决策问题的解决方案，我们会发现这种方法的缺点：一个为解决具体实例而构建的系统在试图解决另一个实例时是无用的如果我们考虑一个有输入的P系统，这个障碍就很容易克服。然后，相同的系统可以解决问题的不同情况下，提供相应的输入多集被引入到输入膜。与其寻找解决问题的单个系统，我们更倾向于设计一个P系统族，使得每个元素在某种意义上决定所有大小相等的实例定义2.5设F是一类识别器P系统。我们说一个决策问题X=（IX，θX）可以在多项式时间内由一个族X =（X（n））n∈N+，of解，我们用XPMCF表示，如果下面是真的：• 族是多项式一致的图灵机;也就是说，存在一个确定的图灵机，在多项式时间内从n N +构造（n）。• 存在一对（g，h）多项式时间可计算函数g：L→n∈N+I<$（n）和h：L→N+使得对每个u∈L，我们有g（u）∈I（h（u）），以及· 族p关于（g，h）是多项式有界的;也就是说，存在多项式函数p，使得对于每个u IX，每个计算（2）在（1）中，（2）是（1），（3）是（1），（4），（5），（6），（|u|）步骤。· 关于（X，g，h），族u是可靠的;也就是说，对于每个u∈IX，它证明了如果存在对输入g（u）的可接受的计算，则θX（u）= 1。· 关于（X，g，h），族f是完备的;也就是说，对于每个u∈IX，98 M.A. 古铁雷斯-纳兰霍等人 理论计算机科学电子笔记123（2005）93-110∈--证明了如果θX（u）= 1，则每个以g（u）为输入的计算都是可接受的。在上面的定义中，我们强制每个P系统<$（n）在以下意义上是连续的：具有相同输入的每个计算产生相同的输出。我们有类PMCF在多项式时间约简和补下是封闭的3在线性时间在这一节中，我们提出了一个线性时间解决方案的分区问题，在P系统的活动膜，不断比较它与解决方案的划分问题可以表述如下：给定一个n个元素的集合A，其中每个元素都有一个“权重”w i N，决定是否存在A分成两个具有相同总权重的子集的划分。我们将使用类型为（n，（w1，.）的元组来表示问题的实例。，wn）），其中n是集合A的大小，并且（w1，.，w n）是来自A的元素的权重的列表。我们可以用自然的方式定义一个与实例中的数据相对应的加法函数w我们通过暴力算法解决问题。该战略可大致分为以下次级目标：• 生成阶段：使用膜分裂为每个子集获得单个膜• 计算阶段：在每个膜中计算其关联子集的权重和其互补子集的权重。• 检查阶段：在每个膜中，将w（B）与w（Bc）进行比较，其中B是相关联的子集。• 输出阶段：根据检查结果输出答案。这里给出的族是<$={（<$（n），<$（n），i（n））：n∈ N}。对于族中的每个元素，输入字母表是n（n）= x1，.，xn，输入膜总是相同的，i（n）= e，P系统n =（Γ（n），{e，r，s}，μ，Me，Mr，Ms，R）定义如下：• 工作字母表：r（n）={a0，a，b0，b，c，d0，d1，d2，e0， . . ，en，g，g′，g′，h0，h1，i1，i2，i4，i5，M.A. 古铁雷斯-纳兰霍等人理论计算机科学电子笔记123（2005）9399eeeeeeeeeep，p′，q，x0， . . . ，xn， Yes， No， No0，z1， . . ，z2n+1，#}.• 膜结构：µ = [ [ ] e[ ] r] s。• 初始多组：Me=e0g;Mr=b0h0和Ms=z1。• 演化规则集R由以下规则组成：（a）[ei]0→[q]-[ei]+，其中i=0， . . ，n.[ei]+→[ei+1]0[ei+1]+，对于i=0， . . ， n−1。这些规则的目标是为每个子集生成一个膜，A.事实上，完全相同的两个计划的规则用于生成阶段的子集和背包的情况下。下面是这些规则的工作原理：在每一步中（根据ei的索引），我们考虑A的一个元素，要么将其添加到与膜相关的子集B中，要么将其放入互补子集Bc中。 注意，膜只有在带负电荷后才能进入检查阶段;带正电荷的膜在物体en出现时会被阻塞（它会溶解，见（i）中的规则）。（b）[x0→a0]0;[x0→p′]+.[xi→xi−1]+，[xi→p<$]−，对于i=1， . . ，n.在开始时，对象x j（其中1 ≤j≤n）的重数编码A的相应元素的权重。它们在系统的定义中不存在，但在开始计算之前，它们作为输入被插入到膜实验室中：对于ea chaj∈A，必须将xj加到输入膜上。在计算过程中，在将元素添加到与膜相关联的子集的同时，给定对象a0和p0来确定该子集的权重，并且使其互补。同样，这些规则方案几乎与用于子集和和背包的计算阶段的规则方案相同（参见[5]，[6]），唯一的区别是，在这里的互补的重量是保持，并在上述文件中，它只是删除。事实上，值得注意的是，索引旋转技术已经在[8]和[10]中使用，以有序的方式处理变量集，即使那里没有权重计算。（c）[q→i1]−e;[p<$→p]−e;[a0→a]−e。当膜带负电时，两个第一阶段（即，生成和计算阶段）结束，然后应用一些转换规则。当比较关联子集w（B）和其互补子集w（B c）的多重性时，Objsa0和p0，其中关联子集w（B）和其互补子集w（B c）的多重性为nc，被重命名用于下一阶段（类似的重命名规则可以是100 M.A. 古铁雷斯-纳兰霍等人 理论计算机科学电子笔记123（2005）93-110eeeeeeeeeeeee在子集和和背包解决方案的设计中发现）。重命名有助于避免检查阶段的规则与生成和计算阶段的规则之间的冲突（d）[a]−e→[]0#;[p]0→[]−e#。这些规则实现了上面提到的比较（也就是说，它们检查w（B）=w（Bc）是否成立）。它们像一个循环一样工作，一个接一个地交替擦除物体a和p，在每一步中改变膜的电荷完全相同的方法可以用来比较工作字母表中任何两个对象的乘数，所以我们再次找到了在解决其他数值问题时可以重复使用（e）[i1→i2]−e;[i2→i1]0.这里描述了控制前一个循环的标记。ij的指数和膜的电荷给出了足够的信息来指出物体的数量a是否大于（小于或等于）物体的数量p。在这里，我们找到了设计中与子集和和背包设计的第一个重要区别。这些计数器被使用，规则的方案取决于检查将持续的步骤数但是现在这个步数取决于集合A的总权重，如果我们想要均匀设计，我们就不能使用这个信息然而，也有好消息：这里使用的规则也可以用于一般情况，因此可以使用此子例程给出子集求和和背包的新版本解决方案。（f）[i1]0→[]+N0.这条规则与下一项中的规则一起负责检查的结果。如果一个子集B→A证明w（B）> w（B c），那么在计算阶段结束时，在与它相关联的膜内的对象p将少于a。这迫使（e）中描述的循环停止：当e不再剩下对象sp时，第n个规则e[i2→i1]-e将beappliedbuttitwiltepossibletoappllyerule[p]0→[]−#ate同时还研究与讨论因此，物体i1将存在于膜中，并且后者将被中性充电，因此将应用规则（f），以否定结果结束检查阶段。(g) [i2→i4c]−e.[c]−e→[]0#;[i4→i5]0.[i5]0→[]+Yes;[i5]−→[]+No.相反，如果w（B）≤w（Bc）成立，则对象a将不存在。M.A. 古铁雷斯-纳兰霍等人理论计算机科学电子笔记123（2005）93101eSSSRReRreSSSSSeeRR在对象P之前被加速。区分p的重数严格大于a的重数的情况和这些重数重合的情况这就是为什么物体c又给出了新的如果[p]0→[]−#，则将电荷转移到该内存范围，并且不将电荷转移到该内存范围。e e是否适用。（h）[p→#]+;[a→#]+。如果在（d）中的规则的检查循环结束之后，膜中仍然存在一些对象p或a，则可以将它们擦除（仅用于“清洁”目的）。（i）[en]+→#。[a0→#]0;[p<$→#]0;[g→#]0.这些规则还执行这在设计中并不重要，但很有帮助。（j）[zi→zi+1]0，对于i=1， . . 、2n.[z2n+1→ d0d1]0.[d1]0→[]+d1。在发送答案之前，系统必须确保所有相关的膜都完成了检查阶段。要做到这一点，首先我们等待2n + 1步，然后我们激活该过程。这样做是为了确保分裂过程结束，因此我们知道，从这一刻起，完成检查阶段的膜，只有它们，将具有正电荷（参见（f）和（g）中的规则检查结束，并注意我们通过（i）中的规则去除多余的膜）。（k）[g]−e→[]−eg<$.[g<$→g<$]+。g[]+→[g]0.正如我们之前所说，我们需要检查所有相关的膜是否完成了检查阶段。这是使用存在于皮肤中的对象g和由r标记的辅助膜来完成的（参见下一组规则）。g必须有2n个拷贝，因为每个相关的膜发送一个拷贝，A的每个子集都有一个相关的膜，总共是2n（l）d0[ ]0→[d0]−.[h0→h1]−r;[h1→h0]+。[b0]−r→[]+b;g<$[]+→[g<$]−。102 M.A. 古铁雷斯-纳兰霍等人 理论计算机科学电子笔记123（2005）93-110SSRRRRSSb[]−r→[rb0]+;[g<$]+→[]−rg<$.[h0]+→[]+d2;[d2]+→[]0d2。由r标记的膜在初始构型中存在，但保持不活动，直到物体d0该膜的目的是在对象集被创建的情况下执行操作，例如，如果在皮肤中没有可用的对象集，则操作将停止。 因此，我们可以检测滑雪区域内是否存在其他目标。这一事实将意味着所有相关的膜已经完成了它们的检查阶段，并且系统准备好发送答案（是或否）。（m）[No→No0]−s.[Yes]−s→[]0Yes。[No0]−s→[]0No.最后，输出过程被激活。在答案发出之前，皮肤膜需要带负电荷。对象d2负责处理这个问题（参见前面的规则集），然后，如果答案是肯定的，则将发送对象Y es，请注意，答案Y es比否定答案有一定的优先级，在这个意义上，我们首先检查是否有任何对象Y es，然后，如果不是这种情况，答案No将被发送出去。这种改变皮肤膜电荷和使用0号辅助对象的小技巧也在其他两个设计中使用，所以希望这个功能也可以保留下来用于未来的设计。3.1关于计算复杂性的上面介绍的设计的主要目标不仅仅是解决划分问题，而是根据一些预先确定的标准（参见2.2小节中介绍的复杂性类）有效地解决这个问题。回想一下，活动膜模型允许我们在计算过程中在多项式时间内创建指数工作空间我们利用这个事实，因此我们只关心时间复杂度（任何计算的蜂窝步骤的数量）和最初需要建立P系统的资源。在这一行中，请注意上面介绍的P系统家族具有递归描述，并且它只需要多项式数量的资源：• 字母表的大小：4n+ 27 ∈ Θ（n）。• 初始膜数：3 ∈Θ（1）。• 初始多重集的大小：5 ∈Θ（1）。• 演化规则数：6n + 39∈ Θ（n）。此外，可以证明该系统是连续的，M.A. 古铁雷斯-纳兰霍等人理论计算机科学电子笔记123（2005）93103eee任何计算的步数是关于大小2的线性顺序的输入multiset。 也就是说，分区∈PMCAM。对于SAT [8]，VALIDITY [10]，Subset-Sum [5]和Knapsack [6]问题，得到并证明了类似的复杂性结果。4规则的一般化：面向编程语言在本节中，我们将概述计算，评论规则如何工作，并概述可以添加到我们打算创建的编程语言的子程序库中的第一条指令。在计算的第一步，应用规则e[ei]0→[q]-[ei]+，对于i= 0。从现在开始，剩下的分配规则反过来，以这种方式，每当一个带负电荷的膜被创建时，它将不再分裂。 与内膜相关联的子集的概念• 与初始膜相关联的子集是空的。• 当一个物体e j出现在一个电中性的膜中时（其中j

下载后可阅读完整内容，剩余1页未读，立即下载