4.3 计算效率分析
对于具有n个变量和m个子句的SAT问题，构造ΠSAT（m，n）的统一算法必要资源可以表示如下：
（1）物质的数量：6mn＋6n＋2m＋4；
（2）初始细胞的数量：2；
（3）初始物质的数量：3；
（4）规则总数：8mn＋8n＋m＋3；
（5）规则的最大长度：3。
对任意的时间映射e：R→N，基于细胞分裂类组织识别膜系统在统一方式下求解SAT问题，系统将在确定的RS步后停止计算。最终，对象yes或no必然会在可行时间内出现在环境中。因此，系统ΠSAT（m，n）是时间无关充分的和时间无关完备的。
如果公式γ是可满足的，则在最多3mn＋7n＋m＋2个RS步后，P系统将停止工作；如果公式γ是不满足的，则在最多3mn＋7n＋m－1个RS步之后，P系统将停止工作。对于这两种情况，产生阶段的RS步最多均为3mn＋7n个RS步；对于检测阶段，前者需要m个RS步，后者最多需要m－1个RS步（因为检测阶段的m条规则不可能全部执行）；而对于输出阶段，前者需要2个RS步，后者不需要RS步。显然，SAT问题可以通过一族类组织识别膜系统在多项式RS步内以时间无关的方式解决。
定理4.2：SAT∈PMC TF－TP（3）
推论4.1：NP∪co－NP⊆PMCTF－TP（3）
显而易见，SAT问题属于NP完全问题。在第4.2节给出的识别P系统中，其通信规则最大长度为3。根据前面的定义以及论述，很容易证明SAT∈PMCTF－TP（3），并且PMCTF－TP（3）在多项式时间归约下以及它的补集都是封闭的。
本章使用细胞分裂的类组织时间膜系统，研究了这类膜系统的计算效率。通过使用细胞分裂类组织膜系统得到了SAT问题的时间无关统一解，其中通信规则的最大长度仅为3，并且规则的执行时间长短对计算结果没有任何影响。证明结果表明，该系统模型可以高效求解NP完全问题。在类组织时间膜系统中，本章采用细胞分裂方法。如果使用细胞分割方法［12-16］，可以考虑在时间无关模式下求解NP完全问题，这仍然是一个公开问题。