膜計算系統(tǒng)求解計算困難問題綜述

宋勃升, 賴樂珊, 李肯立

(湖南大學 信息科學與工程學院, 湖南 長沙 410082)

膜計算是自然計算的分支，它是從生物細胞的結(jié)構(gòu)和功能中抽象出來的計算范式. 自1998年P(guān)?un[1]首次提出膜計算概念以來，學者們提出了許多不同的膜計算模型. 一個膜計算系統(tǒng)包含以下幾個部分：細胞膜內(nèi)的物質(zhì)、進化規(guī)則、控制物質(zhì)轉(zhuǎn)移的蛋白質(zhì)通道、膜分裂和膜分離等. 最早提出的膜系統(tǒng)屬于細胞型膜系統(tǒng)，它的膜結(jié)構(gòu)是分層排列，每個膜包含的區(qū)域內(nèi)含有物質(zhì)多重集和物質(zhì)進化規(guī)則，每個膜內(nèi)的進化規(guī)則通常以極大并行模式執(zhí)行計算過程.

膜計算研究主要分為理論研究和應(yīng)用研究. 理論研究主要關(guān)注各類膜系統(tǒng)變型的可計算性、小通用注冊機和計算復雜性等. 計算復雜性是近年來膜計算領(lǐng)域一個非常重要的研究方向，已經(jīng)證明在膜系統(tǒng)中引入膜分裂操作可以在多項式時間內(nèi)解決NP完全問題，文獻[2-4]證明了幾類膜系統(tǒng)的計算能力上限為復雜類PSPACE，而文獻[5-8]涉及的膜計算模型可以刻畫P#P類. 在膜計算應(yīng)用方面，硅膜啟發(fā)式算法被用于系統(tǒng)生物學中的建模研究：一方面用于優(yōu)化和控制方面的研究；另一方面，膜計算模型可以作為人工細胞系統(tǒng)的形式化表達，并且已經(jīng)有多個側(cè)重于人工細胞系統(tǒng)在合成生物學框架內(nèi)生物實現(xiàn)方面的研究.

本文主要介紹幾類可以有效求解計算困難問題的膜系統(tǒng)，包括介紹活性膜膜系統(tǒng)、膜上帶蛋白膜系統(tǒng)、組織膜系統(tǒng)、帶膜分裂的同向/反向規(guī)則膜系統(tǒng)以及脈沖神經(jīng)膜系統(tǒng)的相關(guān)定義和基本概念[9]；給出了這些膜系統(tǒng)模型的計算效率和計算復雜性；指出了一些可以提高膜系統(tǒng)計算能力的特性；最后給出各類膜系統(tǒng)中存在的一些公開問題.

1 預備知識

多重集M是一個二元組(A,f)，其中f:A→N是一個映射(A是字母表，N是自然數(shù)集合).M的支撐集定義為supp(M)={x∈A|f(x)>0}，多重集的基數(shù)是指該多重集中重復元素的和. 若多重集的支持集是空集(或有限集合)，則該多重集定義為空(或有限的). 如果M1=(A,f1)，M2=(A,f2)是字母表A上的多重集，那么M1和M2的并集定義為M1+M2=(A,g)，其中g(shù)=f1+f2. 用符號P、NP、co-NP和PSPACE表示基本的計算復雜性類型[10]，P#P表示帶預判的多項式時間圖靈機能夠解決的問題類.

定義1一個度為m≥1的膜系統(tǒng)是一個元組

Π=(O,H,μ,w1,…,wm,R,iout),

其中，O是有限字母表；H是膜的標簽集合；μ是度為m的膜結(jié)構(gòu)；w1,…,wm∈O*是m個膜中的初始多重集；R是有限的規(guī)則集合；iout是輸出區(qū)域.

Π的格局是當前時刻膜結(jié)構(gòu)μ和存在于所有膜中的物質(zhì)多重集(初始是w1,…,wm)的元組. 系統(tǒng)的格局通常以最大并行模式(還有其他的規(guī)則使用模式，譬如串行和最小并行等)使用規(guī)則來轉(zhuǎn)換. 當系統(tǒng)沒有可用的規(guī)則時，系統(tǒng)停止，輸出區(qū)域的物質(zhì)多重集為計算結(jié)果.

為了解決判定性問題，通常需要定義識別膜系統(tǒng).

定義2一個度為m≥1的識別膜系統(tǒng)是一個元組

Π=(O,H,μ,Σ,w1,…,wm,R,iin,iout),

其中,字母表O中包含兩個不同的元素yes，no，他們中至少一個包含在初始多重集中，但初始時刻不能出現(xiàn)在環(huán)境中；H是膜的標簽集合；μ是膜結(jié)構(gòu)；存在一個嚴格包含在O中的字母表Σ(輸入字母表)；wi(1≤i≤m)是OΣ上的初始多重集；iin∈{1,…,m}是輸入?yún)^(qū)域，輸出區(qū)域iout是環(huán)境；所有的計算都停止；如果C是該系統(tǒng)的一個計算，那么，當系統(tǒng)停止時，或者yes或者no(但不是兩者)必須出現(xiàn)在環(huán)境中.

一個判定性問題X是一個二元組(IX,θX)，其中，IX是一個有限字母表(它的元素稱為例子)上的一個語言，θX是IX上的一個全局布爾函數(shù)(也就是謂詞)[11].

定義3設(shè)X=(IX,θX)是一個判定性問題，筆者認為X可以在多項式時間內(nèi)被識別膜系統(tǒng)族Π={Πu|u∈IX}解決如果以下條件滿足：

(1)系統(tǒng)族Π是圖靈機在多項式時間內(nèi)統(tǒng)一的，即關(guān)于系統(tǒng)Πu(u∈IX)，存在一個在多項式時間內(nèi)工作的確定性圖靈機；

(2)系統(tǒng)族Π是關(guān)于X充分的，如果對每一個例子u∈IX，系統(tǒng)Πu都存在一個接受的計算，那么θX(u)=1；

(3)系統(tǒng)族Π是關(guān)于X完備的，如果對每一個例子u∈IX，并且滿足θX(u)=1，那么Πu的每一個計算都是一個接受的計算；

(4)系統(tǒng)族Π是多項式有界的，即存在一個多項式函數(shù)p(n)，對每一個u∈IX，系統(tǒng)Πu的所有計算都將在p(|u|)步內(nèi)停止.

因此，系統(tǒng)族Π是判定性問題的一個半統(tǒng)一解.

定義4一個判定性問題X=(IX,θX)在多項式時間內(nèi)可以被一族識別膜系統(tǒng)Π={Π(n)|n∈N}以統(tǒng)一的模式解決如果滿足以下條件：

(1)系統(tǒng)Π是圖靈機在多項式時間內(nèi)統(tǒng)一的，即對于系統(tǒng)Π(n)(n∈N)，存在一個在多項式時間內(nèi)工作的確定性圖靈機；

(2)IX上存在一個多項式時間的計算函數(shù)對(cod,s)，使得

①對于任意一個例子u∈IX，s(u)是一個自然數(shù)，cod(u)是系統(tǒng)Π(s(u))上的一個輸入多重集；

②對每個自然數(shù)n∈N，s(-1) (n)是一個有限集合；

③系統(tǒng)族Π是關(guān)于(X,cod,s)多項式有界的，即存在一個多項式函數(shù)p(n)，對每一個u∈IX，系統(tǒng)Π(s(u)+cod(u))的所有計算都將在p(|u|)步內(nèi)停止；

④系統(tǒng)族Π是關(guān)于(X,cod,s)充分的，即對每一個例子u∈IX，如果系統(tǒng)Π(s(u)+cod(u))存在一個接受的計算，那么θX(u)=1；

⑤系統(tǒng)族Π是關(guān)于(X,cod,s)完備的，即對每一個例子u∈IX，并且滿足θX(u)=1，那么系統(tǒng)Π(s(u)+cod(u))的每一個計算都是一個接受的計算.

因此,系統(tǒng)族Π是判定性問題的一個統(tǒng)一解.

用PMCC表示由C型膜系統(tǒng)族以統(tǒng)一方式在多項式時間內(nèi)可解的一類判定性問題. 類似地，用PMCC*表示由C型膜系統(tǒng)族以半統(tǒng)一方式在多項式時間內(nèi)可解的一類判定性問題.

2 各類膜系統(tǒng)的計算能力

2.1 活性膜膜系統(tǒng)

活性膜膜系統(tǒng)是一類基本的類細胞型膜系統(tǒng)，它的一個重要特征是每個膜上帶有三種電荷+，-或0中的一種[1]. 活性膜膜系統(tǒng)含有膜分裂規(guī)則，通過使用膜分裂規(guī)則，一個膜可以分裂成兩個與原膜標簽相同的膜，原膜中的物質(zhì)也將復制到兩個子代膜中. 在活性膜膜系統(tǒng)中，學者也研究了將膜分裂替換成膜分離，通過使用膜分離操作，原膜內(nèi)的物質(zhì)被分配到子代膜中. 在活性膜膜系統(tǒng)中，還有膜溶解規(guī)則，當特定的物質(zhì)出現(xiàn)在一個膜中時，該膜被溶解，膜內(nèi)的規(guī)則將消失，同時膜內(nèi)的物質(zhì)被釋放到其父膜中.

定義5活性膜膜系統(tǒng)(簡稱AM系統(tǒng))是一個元組

Π=(O,H,μ,w1,…,wm,R,iout)，

其中，O,H,w1,…,wm和iout的概念與定義1中相應(yīng)元素的概念相同，μ中的膜帶指定的電荷+、-或0，R是一個規(guī)則集合，具有如下形式：

初始格局，系統(tǒng)Π中所有膜的電荷都為0，以最大并行模式運行，直到計算終止. 在一個計算步中，每個物質(zhì)最多可用于規(guī)則類型(a)～(e)的一條規(guī)則，每個膜最多可用于規(guī)則類型(b)～(f)的一條規(guī)則.

表1總結(jié)了活性膜膜系統(tǒng)的已知結(jié)果[3,5,12-16]，涉及到膜系統(tǒng)(不)允許使用各種類型的規(guī)則. 表1中的每一列都定義了允許使用規(guī)則類型的特定組合，最后一行顯示了僅使用這些類型規(guī)則的活性膜膜系統(tǒng)可以解決的問題統(tǒng)一解. 讀者可以閱讀其詳細的證明過程參見文獻[17-18].

表1中的結(jié)果是膜結(jié)構(gòu)深度不受限制的活性膜膜系統(tǒng). 當允許非基本膜分裂但膜結(jié)構(gòu)的深度有限時，所得的膜系統(tǒng)可以解決介于P#P和PSPACE之間的復雜類問題[19-20].

表1 識別器帶極化的AM系統(tǒng)統(tǒng)一族的計算能力

Table 1 Computational power of uniform families of recognizer AM systems with polarization

規(guī)則類型計算能力計算能力計算能力進化規(guī)則(a)*XX通訊規(guī)則(b)、(c)XXX膜溶解(d)***基本膜分裂(e)X*非基本膜分裂(f)X求解問題類===在多項式時間內(nèi)PP#PPSPACE

注：X表示允許使用的規(guī)則類型；空白表示不允許使用的規(guī)則類型；*表示對計算能力沒有影響的規(guī)則類型.

2.1.1 無極化活性膜膜系統(tǒng)

無極化活性膜膜系統(tǒng)是指該膜系統(tǒng)中所有膜都不具有電荷(用AM0表示無極化活性膜膜系統(tǒng)). 如表2的最后一列所示，當允許使用所有(a)～(f)類型的規(guī)則時，AM0系統(tǒng)族仍然能夠在多項式時間內(nèi)解決PSPACE完全問題. 然而，如果AM0不允許使用膜溶解規(guī)則，那么該膜系統(tǒng)的計算能力將顯著減弱[21].

表2 識別無極化AM系統(tǒng)族的計算能力

Table 2 Computational power of uniform families of recognizer AM systems without polarization

規(guī)則類型計算能力計算能力計算能力計算能力進化規(guī)則(a)XXX通訊規(guī)則(b)、(c)*XX膜溶解(d)XXXX基本膜分裂(e)XXX非基本膜分裂(f)XX求解問題類=??=在多項式時間內(nèi)PP#PNP∪co-NPPSPACE

注：X表示允許使用的規(guī)則類型；空白表示不允許使用的規(guī)則類型；*表示對計算能力沒有影響的規(guī)則類型.

如果在只允許使用膜溶解和進化規(guī)則的情況下，該膜系統(tǒng)族在多項式時間內(nèi)的計算能力等價于復雜類P(表2中第一列). 如果系統(tǒng)允許使用類型為(b)和(c)的通訊規(guī)則以及限制形式為[a]h→[b]h[b]h(基本膜的對稱分裂)的分裂規(guī)則(e)，那么系統(tǒng)的計算能力不變. 然而，當系統(tǒng)允許使用基本膜分裂時，系統(tǒng)的計算能力有所提升[5](表2中的第二列). 最后，允許使用規(guī)則類型(d)、(e)和(f)的AM0半統(tǒng)一族可以在多項式時間內(nèi)解決NP∪co-NP[22]中的問題.

表2總結(jié)了AM0的一些已知結(jié)果[3,15,21-25]. 關(guān)于無極化具有活性膜膜系統(tǒng)計算能力的綜述可以參考文獻[26-27]，該文討論了進化和通訊規(guī)則的各種限制/擴展條件下對系統(tǒng)計算能力的影響.

公開問題1 含有規(guī)則類型(a)～(e)的AM0多項式統(tǒng)一族的計算能力是否等價于復雜類P(P?un猜想).

公開問題2AM0系統(tǒng)在使用規(guī)則類型(d)、(e)和(f)時的嚴格上下限.

2.1.2 時間無關(guān)的活性膜膜系統(tǒng)

在標準膜系統(tǒng)中，每條規(guī)則的執(zhí)行時間是一個單位時間；而在帶時間的活性膜膜系統(tǒng)中，定義了一個時間函數(shù)，每條規(guī)則的執(zhí)行時間都由該時間函數(shù)確定.文獻[28]定義了時間無關(guān)膜系統(tǒng)，即對任意的時間函數(shù)，系統(tǒng)的計算結(jié)果都相同. 文獻[29]首次提出了在時間無關(guān)模式下求解計算困難問題的概念. 文獻[30]第一次給出了活性膜膜系統(tǒng)族在時間無關(guān)模式下求解SAT問題. 在時間無關(guān)活性膜膜系統(tǒng)中，作者提出了規(guī)則啟動步的概念，即在某一計算步中，至少有一條規(guī)則開始執(zhí)行時，則該計算步被記為一個規(guī)則啟動步. 隨后其他類型的膜系統(tǒng)(譬如膜上帶蛋白質(zhì)膜系統(tǒng)，組織膜系統(tǒng))也被證明可以在時間無關(guān)模式下的求解計算困難問題，其中包括QSAT問題在內(nèi)的PSPACE完全問題.

2.1.3 非流利活性膜膜系統(tǒng)

流利活性膜膜系統(tǒng)是指對給定的非確定型膜系統(tǒng)(給定輸入)，它可以通過不同的計算途徑，最終只能得到一個相同的結(jié)果，或者拒絕或者接受. 在這一小節(jié)，筆者討論非流利活性膜膜系統(tǒng)，即相同的膜系統(tǒng)可以同時產(chǎn)生接受和拒絕計算. 在非確定圖靈機中，如果至少有一個計算被接受，則認為膜系統(tǒng)接受該輸入.

文獻[31]證明了即使沒有膜分裂，非流利膜系統(tǒng)也能夠在多項式時間內(nèi)解決NP完全問題. 文獻[32]證明了深度為1的非流利活性膜膜系統(tǒng)的多項式統(tǒng)一族在使用進化規(guī)則、物質(zhì)送出通訊規(guī)則和基本膜分裂規(guī)則時，可以在多項式時間內(nèi)解決PSPACE問題. 由于非流利膜系統(tǒng)在其計算過程中最多可以使用的計算空間為指數(shù)個，因此文獻[33]給出了EXPSPACE計算能力的上界.

公開問題3非流利活性膜膜系統(tǒng)統(tǒng)一族是否能夠刻畫復雜類PSPACE.

2.2 帶膜分裂的同向/反向規(guī)則膜系統(tǒng)

帶膜分裂的同向/反向規(guī)則膜系統(tǒng)實際上是將同向/反向規(guī)則和膜分裂引入到膜系統(tǒng)中[34]. 同向/反向是指物質(zhì)在細胞或環(huán)境內(nèi)進行位置的移動或交換，物質(zhì)本身不發(fā)生變化. 在同向/反向規(guī)則中，每條規(guī)則可以有任意多個物質(zhì)參與.

同向規(guī)則的形式是(u,in)或(u,out)，多重集物質(zhì)u被送進膜內(nèi)或被送出膜.

反向規(guī)則的形式是(u,out;v,in)，多重集物質(zhì)u被送出膜的同時，多重集物質(zhì)v被送入該膜中.

文獻[34]證明了僅使用同向/反向規(guī)則膜系統(tǒng)具有計算通用性，學者們又提出了該模型的許多變型. 文獻[35]中提出了帶膜分裂的同向/反向規(guī)則膜計算模型，在使用基本膜分裂規(guī)則和通訊規(guī)則長度不超過時，證明了該膜系統(tǒng)可以在線性時間內(nèi)求解NP完全問題(子集和問題)的統(tǒng)一解. 當同向/反向規(guī)則膜系統(tǒng)中允許使用非基本膜分裂時，該膜系統(tǒng)可以在多項式時間內(nèi)求解PSPACE完全問題(QSAT問題)的統(tǒng)一解. 筆者推測PSPACE問題也是帶非基本膜分裂的同向/反向規(guī)則膜系統(tǒng)在多項式時間內(nèi)計算能力的上限.

2.3 膜上帶蛋白的膜系統(tǒng)

受膜上膜蛋白控制物質(zhì)進出細胞這一生物事實的啟發(fā)，P?un等[36-38]提出了膜上帶蛋白的膜系統(tǒng)模型.

定義6帶膜分裂的膜上帶蛋白膜系統(tǒng)是一個元組

Π=(O,P,μ,w1/z1,…,wm/zm,E,R1,…,Rm,io),

其中：O是物質(zhì)的集合，P是蛋白質(zhì)集合，O∩P=?；

μ是膜結(jié)構(gòu)(一顆根樹)；

w1,…,wm是m個膜中的物質(zhì)多重集；

z1,…,zm是m個膜上的蛋白質(zhì)多重集；

E?O是環(huán)境中的物質(zhì)多重集；

R1,…,Rm是m個膜中有限規(guī)則集；

io是輸出區(qū)域.

在帶膜分裂的膜上帶蛋白膜系統(tǒng)中，當使用某條規(guī)則時，該規(guī)則中物質(zhì)的位置可以發(fā)生改變，該物質(zhì)也可能發(fā)生進化，同時與該規(guī)則涉及的膜上的蛋白質(zhì)也可能發(fā)生改變.膜上帶蛋白膜系統(tǒng)有以下幾種規(guī)則的類型(表3)，其中a、b、c和d是物質(zhì)，p和p′是蛋白質(zhì)，i是膜的標簽.

表3 膜上帶蛋白膜系統(tǒng)的規(guī)則類型

使用以下形式表示膜分裂(稱為類型6)，其中p、p′、p″是蛋白質(zhì)(可能相等)：

[p|]i→[p′| ]i[p″| ]i.

膜i可以是非基本膜. 分裂產(chǎn)生的膜與原膜標簽相同，原膜內(nèi)的物質(zhì)和膜上的蛋白質(zhì)(除了p′和p″之外)也將復制到新產(chǎn)生的兩個膜中. 文獻[4]證明了帶膜分裂的膜上帶蛋白膜系統(tǒng)可以在多項式時間內(nèi)求解QSAT問題，該文進一步證明了復雜類PSPACE是該類膜系統(tǒng)計算能力的上界. 文獻[41]證明了帶膜分裂的膜上帶蛋白膜系統(tǒng)可以在多項式規(guī)則啟動步內(nèi)以時間無關(guān)的模式求解QSAT問題.

公開問題4帶膜分裂的膜上帶蛋白膜系統(tǒng)能否在只允許使用“res”類型規(guī)則情況下求解QSAT.

公開問題5膜上帶蛋白膜系統(tǒng)在什么限制條件下可以刻畫計算復雜類P.

2.4 組織膜系統(tǒng)

組織膜系統(tǒng)的基本思想是將細胞型膜系統(tǒng)的樹狀結(jié)構(gòu)推廣到任意圖結(jié)構(gòu)[42-43]. 因此，組織膜系統(tǒng)中任何兩個細胞可以直接進行通訊. 通常組織膜系統(tǒng)中的規(guī)則為同向/反向規(guī)則，近年來，學者們提出了許多組織膜系統(tǒng)的變型[44-48]，并證明了絕大多數(shù)組織膜系統(tǒng)的變型具有圖靈通用性.

定義7一個度為m≥1的組織膜系統(tǒng)是一個元組

Π=(Γ,E,M1,…,Mm,R,iout),

其中：

Γ是物質(zhì)的有限字母表；

E?Γ是初始時刻位于環(huán)境中的物質(zhì)集合；

Mi(1≤i≤m)是初始時刻m個細胞中的有限物質(zhì)多重集；

R是形式為(i,u/v,j)的有限通訊規(guī)則集，i,j∈{0,1,2,…,m}，i≠j，u,v∈Γ*，其中規(guī)則的長度定義為|uv|>0；

iout∈{0,1,2,…,m}是輸出區(qū)域.

當使用規(guī)則(i,u/v,j)時，物質(zhì)多重集u從細胞i送到細胞j，同時物質(zhì)多重集v從細胞j送到i. 如果u=λ或v=λ，則該規(guī)則稱為同向規(guī)則.

用TC表示識別組織膜系統(tǒng). 根據(jù)文獻[49]，得出如下結(jié)果：

P=PMCTC.

2.4.1 帶細胞分裂的組織膜系統(tǒng)

受活性膜膜系統(tǒng)中膜分裂規(guī)則的啟發(fā)，P?un將膜分裂引入到組織膜系統(tǒng)中.

分裂規(guī)則:[a]i→[b]i[c]i，i∈{1,2,…,m},a,b,c∈Γ,i≠iout.

如果細胞i中存在物質(zhì)a，則細胞i分裂成兩個具有相同標簽的細胞，在兩個子細胞中，原始物質(zhì)a分別進化為物質(zhì)b和物質(zhì)c，原細胞中的其他物質(zhì)被復制到兩個子細胞中. 當細胞在分裂時，該細胞不能與其他細胞發(fā)生通訊.

筆者用TDC(k)表示帶細胞分裂且通訊規(guī)則長度最長為k的組織膜系統(tǒng). 當通訊規(guī)則的長度不受限制時，直接省略k. 顯然，當k≥j≥1，TDC(j)?TDC(k)?TDC.

如果通訊規(guī)則的最大長度k=1，則帶細胞分裂識別組織膜系統(tǒng)刻畫復雜類P[50]：

P=PMCTDC(1).

如果通訊規(guī)則的最大長度k=2，則帶細胞分裂識別組織膜系統(tǒng)可以求解NP完全問題[51]:

NP∪Co-NP?PMCTDC(2).

如果通訊規(guī)則的長度k≥4，可以得到如下結(jié)論[6]:

PMCTDC(4)=PMCTDC=P#P.

近年來，學者們對帶細胞分裂的組織膜系統(tǒng)在時間無關(guān)模式下求解NP完全問題進行了深入研究，譬如文獻[52-53]用帶細胞分裂的組織膜系統(tǒng)在時間無關(guān)模式下求解了最大團問題、漢密爾頓路徑問題和子集和問題. 然而，帶細胞分裂的組織膜系統(tǒng)是否能在時間無關(guān)的情況下求解P#P中的問題仍然是個公開問題.

2.4.2 具有細胞分離的組織膜系統(tǒng)

膜分離作為另一種可以增加膜數(shù)量的操作在文獻[54]中被首次提出. 與膜分裂不同，當執(zhí)行膜分離操作時，原細胞中的物質(zhì)被分配到兩個子代膜中. 筆者把字母表Γ分成兩個非空集合，即Γ=Γ1∪Γ2，Γ1,Γ2≠?，Γ1∩Γ2=?.

分離規(guī)則：[a]i→[Γ1]i[Γ2]i，其中i∈{1,2,…,m}，a∈Γ,i≠iout.

細胞分離規(guī)則[a]i→[Γ1]i[Γ2]i能夠被使用當且僅當細胞i中存在物質(zhì)a.當該條規(guī)則被使用時，細胞i被分裂成兩個具有相同標簽的細胞，物質(zhì)a被消耗，細胞i中存在的其他物質(zhì)被分配到兩個子細胞中，這樣，來自集合Γ1的物質(zhì)被分配在第一個細胞中，來自集合Γ2的物質(zhì)被分配在第二個細胞中.

筆者用TSC(k)表示帶細胞分離和通訊規(guī)則的長度至多為k的識別組織膜系統(tǒng)，用TSC表示帶細胞分離和訊規(guī)則長度不受限制的識別組織膜系統(tǒng).

當通訊規(guī)則的長度k=2時，帶細胞分離的組織膜系統(tǒng)刻畫復雜類P[55]:

P=PMCTSC(2).

當通訊規(guī)則的長度k≥3時，帶細胞分離的組織膜系統(tǒng)可以求解NP完全問題[55]：

NP∪Co-NP?PMCTSC(3).

文獻[6]給出了在對通訊規(guī)則長度不受限制情況下的結(jié)論:

PMCTSC=P#P.

文獻[6]中的結(jié)果改進了文獻[2,56]中給出的組織膜系統(tǒng)計算能力的上限PSPACE. 更多有關(guān)帶細胞分裂/細胞分離組織膜系統(tǒng)的計算復雜性和計算效率問題可參見文獻[57-58].

公開問題6研究帶細胞分裂或細胞分離的組織膜系統(tǒng)在只允許使用同向(或只允許使用反向)規(guī)則情況下的計算能力.

2.5 脈沖神經(jīng)膜系統(tǒng)

脈沖神經(jīng)膜系統(tǒng)(簡稱SN P系統(tǒng))是受生物神經(jīng)系統(tǒng)中電脈沖信息傳遞啟發(fā)[59]的一類膜系統(tǒng). 與組織膜系統(tǒng)類似，SN P系統(tǒng)的結(jié)構(gòu)用拓撲有向圖描述，有向圖的節(jié)點對應(yīng)于神經(jīng)元，弧對應(yīng)于突觸. 一個神經(jīng)元同時向所有與其有向弧相連的神經(jīng)元傳遞脈沖. 脈沖在神經(jīng)元中積累(就像活神經(jīng)細胞中的電位)，脈沖數(shù)觸發(fā)控制神經(jīng)元脈沖的激發(fā)規(guī)則.

SN P系統(tǒng)從神經(jīng)元中初始給定的脈沖開始計算，以極大并行模式使用激發(fā)規(guī)則. 計算結(jié)果可以定義為兩個脈沖之間的間隔長度或者指定神經(jīng)元中累積的脈沖數(shù)量.

定義8一個度為m≥1的脈沖神經(jīng)膜系統(tǒng)是一個元組

Π=(O,σ1,…,σm,syn,in,out),

其中：

O={a}是字母表(a為脈沖).

σ1,…,σm是神經(jīng)元，具體形式為σi=(ni,Ri)，1≤i≤m，

其中：

ni≥0是σi中包含的初始脈沖數(shù).

Ri是具有以下兩種形式的有限規(guī)則集：

E/ac→a;d，其中，E是正則表達式，c≥1和d≥0；

as→λ，s≥1，對來自Ri每條類型(1)的規(guī)則E/ac→a;d，都滿足as?(∈)L(E)；

syn?{1,2,…,m}×{1,2,…,m}，對任意的1≤i≤m，均有(i,i)?syn；

in,out∈{1,2,…,m}分別表示輸入和輸出神經(jīng)元.

激發(fā)規(guī)則E/ac→a;d可以使用當且僅當神經(jīng)元σi包含k個脈沖，并且ak∈L(E)，k≥c. 當使用該激發(fā)規(guī)則時，包含該規(guī)則的神經(jīng)元消耗c個脈沖，并且它在d個單位時間后產(chǎn)生一個脈沖，在這d個單位時間內(nèi)，該神經(jīng)元處于關(guān)閉狀態(tài)，不接收新的脈沖.

規(guī)則as→λ稱為遺忘規(guī)則，遺忘規(guī)則可以使用當且僅當神經(jīng)元σi正好包含s個脈沖，當使用遺忘規(guī)則時，σi中消耗s個脈沖. 在每個單位時間中，如果神經(jīng)元σi可以使用Ri中的規(guī)則，那么必須以非確定性的方式隨機使用其中的一條規(guī)則.

為了研究SN P系統(tǒng)的計算效率，學者們引入了能夠在多項式時間內(nèi)產(chǎn)生指數(shù)數(shù)量神經(jīng)元的操作(如神經(jīng)元分裂、神經(jīng)元芽殖等)，證明了該膜系統(tǒng)可以在多項式時間內(nèi)求解NP完全問題[60-63].

公開問題7能否給出帶神經(jīng)元分裂或芽殖的SN P系統(tǒng)的精確刻畫復雜類.

公開問題8有預先計算資源的SN P系統(tǒng)能否精確刻畫復雜類PSPACE.

3 結(jié) 論

本文介紹了幾類常用的膜系統(tǒng)以及其各種變型，分析了各類膜系統(tǒng)(活性膜膜系統(tǒng)、膜上帶蛋白膜系統(tǒng)、組織膜系統(tǒng)、帶膜分裂的同向/反向規(guī)則膜系統(tǒng)以及脈沖神經(jīng)膜系統(tǒng))的計算能力，并給出了一些相關(guān)模型中存在的公開問題.

目前膜計算中研究的計算效率和計算復雜性問題都是考慮在各類膜系統(tǒng)中引入膜分裂、膜分離、膜產(chǎn)生等能使膜數(shù)量增加的操作，利用空間換時間的方式，在指數(shù)個膜內(nèi)同步進行計算. 一個公開問題是如何在不使膜數(shù)量增加的情況下，研究膜系統(tǒng)的計算復雜性.

環(huán)境對各類膜系統(tǒng)的計算能力起著重要作用，因為筆者通常假設(shè)環(huán)境中的每種物質(zhì)都是任意多的. 一個公開問題是研究各類膜系統(tǒng)在環(huán)境中物質(zhì)為空集或者環(huán)境中每種物質(zhì)的數(shù)量為有限時的計算能力.