第2章　基于促进剂的时间活性膜P系统

活性膜P系统作为一类受生物启发的计算模型，其中的每条规则在系统运行过程中都具有相同的执行时间。基于该模型，SAT问题获得了有效求解［1-5］。另外，有学者提出一些基于活性膜P系统的新变体，例如不带极性的活性膜P系统［6-8］、异步活性膜P系统［9］等。但是在这些研究成果中，都假设系统中每条规则具有一个精确且相同的执行时间，即在一个单位时间内执行结束，使得现有膜系统的鲁棒性和容错性不够好。从生物学角度来讲，不同生化反应所需时间往往难以预知。因此，有必要构造出与规则的执行时间无关，从而具有良好鲁棒性的活性膜P系统。最近，虽然有部分学者尝试使用时间活性膜P系统来求解NP完全问题［10-12］，但是计算效率提升不够显著。

文献［13］首次提出了促进剂的概念，并将其引入转移P系统进行改进，提出了基于促进剂的时间活性膜P系统，以提高系统的计算效率。在该类系统中，可以通过促进剂引导规则的执行，从而将现有模型中膜上的三类电荷减少到两类。有学者将促进剂引入其他膜系统中［14-16］，也取得了良好效果。

因此，本章首先建立基于促进剂的时间活性膜P系统，然后基于该模型构造了两种方法在多项式时间内对SAT问题进行求解，即半统一和统一的方法。对于这两种方法，系统中规则的执行时间长短对计算结果没有任何影响。最后，使用注册机证明了任何图灵可计算数都可通过这类膜系统产生。研究结果表明，本书提出的模型在求解NP完全问题中相比同类系统具有更好的计算效率。