宋勃升, 賴樂珊, 李肯立

(湖南大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長(zhǎng)沙 410082)

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)IX上存在一個(gè)多項(xiàng)式時(shí)間的計(jì)算函數(shù)對(duì)(cod,s)，使得

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

io是輸出區(qū)域.

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

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

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

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

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

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

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

2.4 組織膜系統(tǒng)

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

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

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

其中：

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

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

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

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

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

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

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

P=PMCTC.

2.4.1 帶細(xì)胞分裂的組織膜系統(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.

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

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

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

P=PMCTDC(1).

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

NP∪Co-NP?PMCTDC(2).

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

PMCTDC(4)=PMCTDC=P#P.

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

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

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

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

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

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

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

P=PMCTSC(2).

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

NP∪Co-NP?PMCTSC(3).

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

PMCTSC=P#P.

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

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

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

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

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

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

Π=(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是正則表達(dá)式，c≥1和d≥0；

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

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

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

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

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

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

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

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

3 結(jié) 論

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

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

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