2.4.1 半统一方法
对于具有n个变量和m个子句的SAT问题，构造ΠSAT-semi（m，n）半统一算法的必要资源可以表示如下。
（1）物质的数量：2m＋5n＋3；
（2）初始膜的数量：2；
（3）初始物质的数量：2；
（4）规则总数：m＋7n＋5。
对于基于促进剂的时间活性膜P系统在半统一方式下求解SAT问题，系统将在确定的RS步后停止计算。对任意的时间映射e：R→N，最终，对象yes或no必然会在可行的时间内出现在环境中。因此，系统ΠSATsemi（m，n）是时间无关充分的和时间无关完备的。
如果CNF公式是可满足的，则在最多m＋6n＋4个RS步后，系统将停止工作；如果CNF公式是不满足的，则在最多m＋6n－1个RS步之后，系统将停止工作。对于这两种情况，产生阶段RS步最多为6n个RS步；对于检测阶段，前者需要m个RS步，后者最多需要m－1个RS步（因为检测阶段的m条规则不可能全部执行）；而对于输出阶段，前者需要4个RS步，后者不需要RS步。显然，系统的整个计算是时间无关线性有界的。
在文献［10］中，通过活性膜P系统在时间无关模式下求解了SAT问题。该文献使用分裂规则，新产生的膜与原始膜之间具有不同的膜标签。随后，这一结果在文献［11］中得到改进：新产生的膜与原始膜具有相同的膜标签。本章通过使用促进剂获得了与文献［11］相同的结果，即使用膜分裂规则e而不是扩展类型e′。而且，与文献［10］和［11］中构造的P系统相比，本章构造的P系统没有使用文献［11］中提到的f类规则［关于f类规则的更多细节，参见文献［11］。此外，本章提出的P系统将膜上电荷从三类简化为两类。通过该系统，使用较少类型的规则和仅具有两类膜上电荷的P系统仍然可以在线性RS步内高效地解决SAT问题。
就目前而言，对于一个膜系统的计算效率高低没有统一的评价标准。如果一个P系统具有较好的性能，本书提出从以下几个方面进行评价：
（1）使用较少的物质；
（2）使用较少数量的规则，而且规则长度尽量短；
（3）膜结构尽量简单；
（4）较少地使用其他计算资源，例如膜上电荷的种类增加了计算资源；
（5）算法复杂度较低，如时间复杂度尽量低。在时间膜系统中，考虑系统的RS步。
本章仅考虑使用膜分裂规则e的时间活性膜P系统。在这种情况下，与文献［11］中的时间膜系统相比，本章构建的P系统需要更少的计算资源和RS步（见表2-1）。
表2-1 半统一方法中计算资源和RS步比较
