1.3.3 时间无关模式下求解NP难问题
定义1.5：对于一个二元组的判定性问题X＝（IX，θX），IX是有限字母表上的一个语言，它的元素称为例子。θX是IX上的全局布尔函数。Π＝｛Π（n）|n∈N｝表示一族识别膜系统。
对于一个判定性问题，其结果为“yes”或者“no”。在问题X上有一对多项式可计算函数（cod；s）。令Π＝｛Π（n，e）|n∈N｝是一族识别时间膜系统，系统中规则的执行时间由时间映射e确定。Π计算实例的解，并且解的正确性不依赖于规则的执行时间，则该解称为问题X由系统Π计算出的时间无关解。
定义1.6：一个判定性问题X＝（IX，θX）在多项式RS步内被一族识别时间膜系统Π＝｛Π（n）|n∈N｝以统一的方式解决，需要满足以下条件：
（1）系统族Π的图灵机在多项式时间内是统一的；也就是说对于系统Π（n），存在一个确定性图灵机，可以在多项式时间内工作，构建的系统仅仅与问题的大小有关。
（2）e为任意的时间映射，在IX上存在一个多项式时间的计算函数对（cod，s），使得：
①对于任意一个例子u∈IX，s（u）是一个自然数，cod（u）作为系统Π（s（n））的一个输入多重集；
②系统族Π是关于（X，cod，s）时间无关充分的，即对每一个算例u∈IX，都存在一个带输入cod（u）的系统Π（s（u），e）接受的计算，则θX（u）＝1；
③系统族Π对于（X，cod，s）是时间无关计算完备的，即对每一个算例u∈IX，并且满足θX（u）＝1，那么带输入cod（u）系统Π（s（u），e）的每一个计算都是一个接受的计算；
④系统族Π是关于（X，cod，s）时间无关多项式有界的，即对每一个u∈IX，存在一个多项式函数p（n），带输入cod（u）系统Π（s（u），e）的所有计算在p（｜u｜）RS步内停止。
上述（1）（2）条件满足了，就称系统族Π是求解某个判定性问题的一个时间无关统一解。统一方法与半统一方法相比，半统一方法是对一个具体的例子进行求解，而统一方法可以解决任意给定大小的例子。对于判定性问题的时间无关半统一解的定义与定义1.6类似，因此就不再对其进行描述。