帶通道狀態(tài)通訊膜系統(tǒng)的研究綜述

宋勃升， 李艷艷， 曾湘祥

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

在生物啟發(fā)式計算或者自然計算的領(lǐng)域內(nèi)，存在一個快速發(fā)展的分支：膜計算，由歐洲科學院院士P?un[1]于1998 年在芬蘭圖爾庫計算機科學中心訪學時首次提出，它是從活細胞的組織和器官的結(jié)構(gòu)以及功能中抽象出來的. 膜系統(tǒng)(又稱為P系統(tǒng))是膜計算研究中計算模型的統(tǒng)稱，它們是分布式和并行計算設(shè)備. 根據(jù)活細胞內(nèi)部的真實膜結(jié)構(gòu)，許多類型的膜系統(tǒng)已經(jīng)被提出[2-5]，主要有兩類P系統(tǒng)：細胞型P系統(tǒng)[1,4](一個細胞中的膜是以一個層次結(jié)構(gòu)排列)和組織型P系統(tǒng)[4,6]，或者神經(jīng)型P系統(tǒng)[7](如一個組織或一個神經(jīng)網(wǎng)絡(luò)置于任意圖節(jié)點中的膜結(jié)構(gòu)). 根據(jù)生物活細胞具有不同的生物特征，研究者們又提出了許多新型的膜系統(tǒng)，例如，帶催化劑的膜系統(tǒng)[8]、帶促進劑/抑制劑的膜系統(tǒng)[9]和剪切膜系統(tǒng)[10]等.

膜計算的研究課題主要聚焦在理論分析和現(xiàn)實生活問題的應用上. 一方面，隨著各種P系統(tǒng)的引入，許多不同種類P系統(tǒng)的計算能力以及計算復雜性已經(jīng)被深入地研究[11-15]. 結(jié)合計算機科學中的基本概念，在理論推導中，學者們設(shè)計了各種不同的規(guī)則執(zhí)行方式，例如，串行模式[16]、極小并行模式[17]、極大并行模式[18]和扁平極大并行模式[19]. 在理論分析方面，主要通過與圖靈機比較來證明多數(shù)膜系統(tǒng)是具有圖靈完備性的，即這些P系統(tǒng)的計算能力與通用圖靈機等價[20-24]. 同時，受細胞膜的分離、分裂以及生成等生物活動的啟發(fā)，膜系統(tǒng)中存在細胞分離[1](1)Sosík P, Cienciala L. Computational power of cell separation in tissue P systems[J]. Information Sciences, 2014, 279: 805-815.、 細胞分裂[25]以及細胞生成[26]等規(guī)則，通過這些規(guī)則的使用，細胞可以生成指數(shù)多個細胞，通過以空間換取時間的方式有效地求解NP完全問題[27-29]以及PSPACE完全問題[30-34]. 另一方面，研究膜計算的實際應用也非常有趣[35-37]，例如，P系統(tǒng)可以應用到生物系統(tǒng)和合成生物學[38]中，可以改進人工智能算法[39-43]，還可以用于電路系統(tǒng)的設(shè)計以及生態(tài)系統(tǒng)的建模[44-45]. 關(guān)于P系統(tǒng)的詳細信息，讀者可以查閱文獻[46]. 更詳盡的細節(jié)以及最新的參考資料可以在網(wǎng)址http://ppage.psystems.eu 上找到.

通訊P系統(tǒng)是一類受活細胞中物質(zhì)跨膜移動的生物現(xiàn)象啟發(fā)而得來的膜系統(tǒng)，最早提出來是在文獻[47]中. 這類P 系統(tǒng)是一類通過使用同向/異向轉(zhuǎn)運規(guī)則代替進化規(guī)則的計算模型，其中,同向轉(zhuǎn)運規(guī)則的形式是(u,in) 或者(u,out)，異向轉(zhuǎn)運規(guī)則的形式是(u,out;v,in). 該類P系統(tǒng)的計算理論研究廣泛，比如計算能力[48-50]，計算有效性[51]和生成語言的能力[52].

膜計算中有一類通訊P系統(tǒng)被提出并且得到了深入的研究，這里稱為帶有通道狀態(tài)的通訊P系統(tǒng)，其中，通道上的狀態(tài)用來控制細胞間的通訊以及細胞與環(huán)境間的通訊. 對于通訊，如果從不同的角度來看，那么會有兩種情況：其一，細胞間會有與狀態(tài)相關(guān)的鏈接，并且細胞會使用這些狀態(tài)來控制細胞間的通訊；其二， 通訊的完成通過同向/異向規(guī)則的使用. 本文主要圍繞著帶有通道狀態(tài)的通訊P 系統(tǒng).首先，對帶有通道狀態(tài)的細胞型通訊P系統(tǒng)，帶有通道狀態(tài)的組織型通訊P系統(tǒng)以及帶有通道狀態(tài)的識別通訊P系統(tǒng)的基本概念進行了簡單的介紹；其次，對這兩類通訊P系統(tǒng)的計算能力和計算復雜性分別進行了概述；最后，給出了對這類通訊P 系統(tǒng)的總結(jié)以及對未來的展望.

1 帶有通道狀態(tài)通訊膜系統(tǒng)的基本概念

本節(jié)主要介紹帶有通道狀態(tài)的細胞型和組織型通訊P系統(tǒng)的概念，模型中涉及有關(guān)形式語言的知識，讀者可以參考文獻[53].

1.1 帶有通道狀態(tài)的通訊膜系統(tǒng)

帶有通道狀態(tài)的細胞型通訊膜系統(tǒng)是由Song等[54]首次提出的，該模型使用的是帶有通道狀態(tài)的同向/異向轉(zhuǎn)運規(guī)則，且規(guī)則以極大并行的方式執(zhí)行，具體概念如下.

定義1一個度為q≥1的帶有通道狀態(tài)的細胞型通訊膜系統(tǒng)是一個元組

Π=(Γ,K,ε,μ,1,…,q,s1,…,sq,1,…,q,iout),

其中：

?Γ是一個有限字母表，ε?Γ；

?K是一個狀態(tài)字母表(與Γ的交集為空)；

?μ是一個含有q個節(jié)點的根樹，用1,…,q來標記；

?si(1≤i≤q)是通道狀態(tài)；

- 同向規(guī)則：(s,(u,out),s′)或(s,(u,in),s′)，s,s′∈K，u∈Γ+；

- 異向規(guī)則：(s,(u,out;v,in),s′)，s,s′∈K，u,v∈Γ+；

?iout∈{0,1,…,q}.

規(guī)則(u,out)，(u,in)(或(u,out;v,in))的長度定義為|u|(或|u|+|v|).

筆者注意到一個非常重要的限制是兩個相鄰區(qū)域之間最多一個通道，每個步驟的狀態(tài)都來自于K. 這個不會限制相鄰區(qū)域間的通訊，因為一個通道的兩個方向上都允許物質(zhì)的移動.

如果膜i和它的父區(qū)域p(i)之間的通道狀態(tài)為s，且膜i中包含多重集合u，那么此時在格局中應用一條同向規(guī)則(s,(u,out),s′). 當這樣一條同向轉(zhuǎn)運規(guī)則被應用時，多重集合u被發(fā)送到區(qū)域p(i)，且區(qū)域i和區(qū)域p(i)之間的通道狀態(tài)從s變?yōu)閟′.

如果膜i和它的父區(qū)域p(i)之間的通道狀態(tài)為s，且區(qū)域p(i)中包含多重集合u，那么此時在一個格局中應用一條同向轉(zhuǎn)運規(guī)則(s,(u,out),s′). 當這樣一條規(guī)則被應用時，多重集合u將從區(qū)域p(i) 進入膜i中，且區(qū)域i與區(qū)域p(i)之間的通道狀態(tài)由s變?yōu)閟′.

如果膜i和它的父區(qū)域p(i)之間的通道狀態(tài)為s，且膜i中包含多重集合u，同時膜i的父區(qū)域中包含多重集合v，那么此時在一個格局中應用一條反向轉(zhuǎn)運規(guī)則(s,(u,out;v,in),s′). 當使用這樣一條規(guī)則時，多重集合u從膜i發(fā)送到區(qū)域p(i)，同時，多重集合v從區(qū)域p(i)發(fā)送到膜i，且區(qū)域i與區(qū)域p(i)之間的通道狀態(tài)由s變?yōu)閟′.

已經(jīng)證明了該類型P系統(tǒng)具有圖靈通用性. 除此之外，學者們還提出了具有細胞分裂的帶有通道狀態(tài)的細胞型P 系統(tǒng)[55]，同樣已經(jīng)證明具有圖靈通用性，且此類型膜系統(tǒng)還可以解決哈密頓回路問題.

帶有通道狀態(tài)的組織型通訊P系統(tǒng)是由Freund等[56]首次提出的，該模型使用的是帶有通道狀態(tài)的同向/異向轉(zhuǎn)運規(guī)則，且規(guī)則以極大并行的方式執(zhí)行，具體概念如下.

定義2一個度為q≥1的帶通道狀態(tài)的組織型通訊膜系統(tǒng)是一個元組

Π=(Γ,T,K,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,,iout),

其中：

?Γ是一個有限字母；

?T?Γ是一個結(jié)束物質(zhì)的字母表；

?K是一個狀態(tài)的字母表；

?ε?Γ是初始時刻位于環(huán)境中的物質(zhì)集合，所有可用的物質(zhì)都有任意多的數(shù)量；

?ch?{(i,j)|i,j∈{0,…,q},i≠j}是細胞間通道或細胞與環(huán)境間通道的集合，在ch中最多出現(xiàn)(i,j)，(j,i)其中之一(0標記環(huán)境)；

?R(i,j)是具有如下形式的有限規(guī)則集合(與通道(i,j)∈ch有關(guān))：

- 同向規(guī)則：(s,u/λ,s′)，s,s′∈K，u∈Γ+；

- 異向規(guī)則：(s,u/v,s′)，s,s′∈K，u,v∈Γ+，|u|>0，|v|>0；

?iout∈{0,1,…,q}.

筆者注意到一個重要的限制是兩個已給細胞之間最多存在一條通道，通道以有序?qū)?i,j)的形式給出，并且通道上有來自于K的狀態(tài). 這個不會限制兩個細胞間或者細胞和環(huán)境之間的通訊，因為通道上的兩個方向都允許物質(zhì)的移動. 規(guī)則(s,u/λ,s′)、(s,λ/u,s′) 或者(s,u/v,s′)的長度分別為|u|和|u|+|v|.

如果區(qū)域i和區(qū)域j之間通道的狀態(tài)為s，且區(qū)域i包含對象的多重集合u，(或者區(qū)域j包含對象的多重集合u)，那么此時在一個格局中使用同向規(guī)則(s,u/λ,s′)∈Ri,j(或(s,λ/u,s′)∈Ri,j). 當使用這樣的規(guī)則時，多重集合u被發(fā)送到區(qū)域j(或者區(qū)域i)，且區(qū)域i和區(qū)域j之間的通道狀態(tài)由s變?yōu)閟′.

如果區(qū)域i和區(qū)域j之間通道的狀態(tài)為s，且區(qū)域i包含對象的多重集合u，同時區(qū)域j包含對象的多重集合v，那么此時在一個格局中使用異向規(guī)則(s,u/v,s′)∈Ri,j. 當使用這樣的規(guī)則時，多重集合u將從區(qū)域i發(fā)送到區(qū)域j，多重集合v將從區(qū)域j發(fā)送到區(qū)域i，且區(qū)域i和區(qū)域j之間的通道狀態(tài)由s變?yōu)閟′.

已經(jīng)證明該系統(tǒng)具有圖靈通用性. 除此之外，學者們還提出了帶有細胞分裂的帶通道狀態(tài)的組織型通訊P 系統(tǒng)，單向[57-59]帶有細胞分裂帶通道狀態(tài)的組織型通訊P系統(tǒng)[60]，它們不僅具有圖靈通用性，而且可以解決NP完全問題.

下面將介紹帶有細胞分裂和通道狀態(tài)的通訊P系統(tǒng)以及相應的識別P系統(tǒng)的基本概念.

1.2 帶細胞分裂和通道狀態(tài)的通訊膜系統(tǒng)

定義3一個度為q≥1的帶細胞分裂和通道狀態(tài)的細胞型通訊膜系統(tǒng)是一個元組

Π=(Γ,K,ε,μ,1,…,q,s1,…,sq,1,…,q,iout),

其中：

?Γ是一個物質(zhì)(或符號)的字母表，又稱為一個有限非空集合；

?K是一個通道狀態(tài)的字母表，表示一個有限非空集合且Γ∩K=?；

?ε是Γ的一個子集，代表初始位于Π環(huán)境中的物質(zhì)集合；

?μ是一個由1,…,q標記的有q個節(jié)點的根樹，表示這個系統(tǒng)的框架；

?si，1≤i≤q是K上的通道狀態(tài)，它們代表每個區(qū)域的初始狀態(tài)；

?Ri，1≤i≤q是每個區(qū)域i中規(guī)則的有限集，有下述的形式：

- 通訊規(guī)則：

- 同向規(guī)則：(s,(u,out),s′)或(s,(u,in),s′)，s,s′∈K，u∈Γ+；

- 異向規(guī)則：(s,(u,out;v,in),s′)，s,s′∈K，u,v∈Γ+；

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

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

定義4 一個度為q≥1的帶細胞分裂和通道狀態(tài)的組織型通訊膜系統(tǒng)是一個元組

Π=(Γ,T,K,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,iout),

其中：

?Γ是一個有限字母；

?T?Γ是一個終止字母表；

?K是一個狀態(tài)的字母表；

?ε?Γ是初始時刻位于環(huán)境中的物質(zhì)集合，所有可用的物質(zhì)都有任意多的數(shù)量；

?ch?{(i,j)|i,j∈{0,…,q},i≠j}是細胞間通道或細胞與環(huán)境間通道的集合;

?R(i,j)是具有如下形式的有限規(guī)則集合(與通道(i,j)∈ch有關(guān))：

- 通訊規(guī)則：

- 同向規(guī)則：(s,u/λ,s′)，s,s′∈K，u∈Γ+；

- 異向規(guī)則：(s,u/v,s′)，s,s′∈K，u,v∈Γ+，|u|>0，|v|>0；

- 分裂規(guī)則：

- [a]i→[b]i[c]i，a,b,c∈Γ，i∈{1,…,q}，i≠iout；

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

1.3 帶細胞分裂和通道狀態(tài)的識別通訊膜系統(tǒng)

定義5一個度為q≥1的帶有細胞分裂和通道狀態(tài)的細胞型識別通訊膜系統(tǒng)是一個元組

Π=(Γ,K,ε,μ,∑,1,…,q,s1,…,sq,1,…,q,iin,iout),

其中：

?(Γ,K,ε,μ,∑,1,…,q,s1,…,sq,1,…,q,iout) 是一個度q≥1的帶有細胞分裂和通道狀態(tài)的細胞型通訊膜系統(tǒng)；

?Γ有兩個不同的物質(zhì)yes和no；

?∑是一個嚴格包含于Γ中的輸入字母表，使得ε??！疲?/p>

?iin∈{1,…,q}是輸入細胞，且iout=0；

?所有的計算停止；

在這個系統(tǒng)中，規(guī)則的集合中包含細胞分裂規(guī)則，即可以產(chǎn)生2n個細胞，由此可見這個系統(tǒng)可以采用空間換時間的方式來解決HPP問題.

定義6一個度為q≥1的帶有細胞分裂和通道狀態(tài)的組織型識別通訊膜系統(tǒng)是一個元組

Π=(Γ,T,K,∑,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,iin,iout),

其中：

?(Γ,T,K,∑,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,iout) 是一個度q≥1的帶有細胞分裂和通道狀態(tài)的組織型通訊膜系統(tǒng)；

?Γ有兩個不同的物質(zhì)yes和no；

?∑是一個嚴格包含于Γ中的輸入字母表；

?iin∈{1,…,q}是輸入細胞，且iout=0；

?所有的計算停止；

在這個系統(tǒng)中，規(guī)則的集合中包含細胞分裂規(guī)則，即可以產(chǎn)生2n個細胞，由此可見這個系統(tǒng)可以采取空間換時間的方式來解決SAT問題.

對于帶有細胞分裂和通道狀態(tài)的識別通訊膜系統(tǒng)來說，如果物質(zhì)yes出現(xiàn)在與計算停止狀態(tài)相關(guān)的環(huán)境中，且在計算的非停止狀態(tài)中沒有出現(xiàn)物質(zhì)yes和no，那么就稱計算為一個接受計算，否則，就稱計算為拒絕計算.

2 帶通道狀態(tài)通訊膜系統(tǒng)的計算能力和計算復雜性

本節(jié)首先介紹帶有細胞分裂和通道狀態(tài)的通訊P系統(tǒng)求解判定性問題的概念，然后再分析這些膜系統(tǒng)的計算能力，最后給出這些膜系統(tǒng)的計算復雜性.

接下來，根據(jù)文獻[61]，筆者定義用同向/異向規(guī)則的帶有細胞分裂和通道狀態(tài)的識別通訊膜系統(tǒng)在統(tǒng)一模式下求解判定性問題.

定義7在多項式時間內(nèi)可以由一族帶有細胞分裂和通道狀態(tài)的識別通訊膜系統(tǒng)∏={Π(n)|n∈}以一種統(tǒng)一的模式解決一個判定性問題X=(IX,θX)，如果滿足下述的條件：

?一族∏是通過圖靈機在多項式時間內(nèi)統(tǒng)一的，也就是說存在一個多項式時間內(nèi)工作的確定性圖靈機，且這個確定性圖靈機可以構(gòu)建系統(tǒng)Π(n)(n∈)；

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

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

- 對每個自然數(shù)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)) 的每一個計算都是一個接受的計算.

2.1 帶有通道狀態(tài)的通訊膜系統(tǒng)的計算能力

本小節(jié)首先介紹帶有通道狀態(tài)的類細胞或類組織通訊膜系統(tǒng)的計算能力，然后再分別介紹了帶有細胞分裂和通道狀態(tài)的類細胞或類組織通訊膜系統(tǒng)的計算復雜性問題.

在介紹定理之前，首先給出各種符號的含義. 一般，NFIN表示正整數(shù)所有有限集的族，NMAT表示無外觀檢測矩陣文法產(chǎn)生的正整數(shù)集合的族，NRE表示自然數(shù)遞歸可枚舉集的族.

根據(jù)文獻[54-55]，對于帶有通道狀態(tài)的細胞型通訊膜系統(tǒng)，筆者有如下的定理展現(xiàn)其計算能力.

定理1根據(jù)文獻[54]，對于帶有通道狀態(tài)，使用同向/異向規(guī)則的細胞型通訊膜系統(tǒng)來說，其具有如下的計算能力，其中，NOPm(statek,symt1,antit2)表示該類膜系統(tǒng)計算的所有數(shù)字集合的族，且該類膜系統(tǒng)有m個膜，k個狀態(tài)，以及使用規(guī)則長度最長為t1的同向規(guī)則和規(guī)則長度最長為t2的異向規(guī)則. 如果在膜系統(tǒng)中只使用了同向規(guī)則(或者異向規(guī)則)，那么由膜系統(tǒng)計算得來的所有數(shù)字集合的族簡單地記為NOPm(statek,symt1)(或者NOPm(statek,antit2)).如果參數(shù)m,k,t1,t2沒有限制，那么它們可以用*來代替.

?NOP*(state*,anti2)?NFIN；

?NOP*(state2,sym1)?NFIN；

?NOP1(state1,anti4)=NOP1(state*,sym1,anti2) =NMAT；

?NOP2(state*,sym1)=NRE；

?NOP2(state4,anti2)=NRE；

?NOP2(state2,anti3)=NRE；

?NOP2(state1,anti3)=NRE；

?NOP2(state3,sym1,anti2) =NRE.

定理2根據(jù)文獻[55]，對于帶有通道狀態(tài)，使用協(xié)同同向規(guī)則，工作在扁平極大并行模式的細胞型通訊膜系統(tǒng)來說，其具有如下的計算能力，其中，NOPm(statek,symt,flat)表示由m個膜，k個狀態(tài)，只使用規(guī)則長度最長為t的同向規(guī)則組成且以扁平極大并行方式工作的膜系統(tǒng)計算的所有自然數(shù)集合的族. 如果參數(shù)m,k,t沒有限制，那么它們可以用*來代替.

?NOP2(state*,sym1,flat)=NOP2(state4,sym2,flat)=NOP2(state2,sym3,flat)=NRE；

?NOP1(state1,sym3,flat)=NRE；

?NOP1(state*,sym2,flat)=NRE；

?NOP2(state3,sym2,flat)=NRE.

定理3根據(jù)文獻[56]，對于帶有通道狀態(tài)的組織型通訊膜系統(tǒng)來說，其具有如下的計算能力. 一般來說，系統(tǒng)Π計算得來的所有向量的集合使用Ps(Π)來表示.PsOtpm(statek,antii)表示系統(tǒng)計算的向量集合Ps(Π)的族，其中這個系統(tǒng)有m個細胞，k個狀態(tài)，使用形式為(s,x/y,s′)的規(guī)則，|x|≤i，|y|≤i. 當參數(shù)m,k,i沒有限制時，可以使用*來代替.MAT表示矩陣文法生成的語言族且PsCF?PsMAT?PsRE.

?PsMAT?PsOtp1(state*,anti1)；

?PsMAT?PsOtp1(state1,anti2)；

?PsOtp1(state*,anti*)?PsMAT；

?PsMAT=PsOtp1(statek,antii)=PsOtp1(state*,antij)，k≥1，i≥2，j≥1，每個k,i,j也可以等于*；

?PsRE=PsOtpm(state*,antii)，m≥2，i≥1；

?PsRE=PsOtpm(statek,antii)，m≥2，k≥1，i≥2；

?PsRE=PsOtp*(statek,antii)，k≥3，i≥1.

定理4根據(jù)文獻[59]，對于帶有通道狀態(tài)，工作在扁平極大并行模式下的組織型通訊膜系統(tǒng)來說，其具有如下的計算能力. 系統(tǒng)Π計算得來的所有向量的集合使用Ps(Π)來表示.PsOtpm(statek,symt1,antit2,flat)表示系統(tǒng)計算的向量集合的族，其中，這個系統(tǒng)有m個細胞，k個狀態(tài)，使用規(guī)則長度最長為t1的同向規(guī)則和規(guī)則長度最長為t2的異向規(guī)則，flat表示通道上的規(guī)則以扁平極大并行的方式使用. 當參數(shù)m,k,i沒有限制時，可以使用*來代替.

?PsOtp*(state*,anti2,flat)?PsFIN；

?PsOtp1(state1,sym3,flat)=PsRE；

?PsOtp2(state*,sym1,flat)=PsRE；

?PsOtp*(state4,sym1,flat)=PsRE.

?NOtP2m(state*,sym1)=NRE；

?NOtP2m(state4,sym2)=NRE；

?NOtP*m(state5,sym1)=NRE.

2.2 帶有細胞分裂和通道狀態(tài)的通訊膜系統(tǒng)的計算復雜性

定理6 根據(jù)文獻[55]，帶有細胞分裂和通道狀態(tài)的細胞型通訊膜系統(tǒng)可以解決哈密頓回路問題，其計算復雜性如下，CCDeP(k)表示一類帶有細胞分裂和通道狀態(tài)，通訊規(guī)則長度最長為k的細胞型通訊膜系統(tǒng)，PMCCCDeP(k)表示由CCDeP(k)在多項式時間內(nèi)解決的所有判定性問題的集合.

?HPP∈PMCCCDeP(1)；

?NP∪co-NP?PMCCCDeP(1).

定理7根據(jù)文獻[59]，帶有細胞分裂和通道狀態(tài)，工作在扁平極大并行模式下的組織型通訊膜系統(tǒng)可以解決SAT問題，其計算復雜性如下，PMCTSDC(k)來表示由帶有細胞分裂和通道狀態(tài)，通訊規(guī)則長度最長為k的組織型識別通訊膜系統(tǒng)在多項式時間內(nèi)以統(tǒng)一的方式解決的所有判定性問題的集合.

3 結(jié)論與展望

本文主要介紹了帶有通道狀態(tài)的通訊膜系統(tǒng)，包括帶有通道狀態(tài)的細胞型通訊膜系統(tǒng)和帶有通道狀態(tài)的組織型通訊膜系統(tǒng). 本文首先分別對這兩類膜系統(tǒng)的基本概念做了簡要的介紹；其次分別介紹了帶有通道狀態(tài)的通訊膜系統(tǒng)的一些變形：帶細胞分裂和通道狀態(tài)的組織型識別通訊膜系統(tǒng)，帶細胞分裂和通道狀態(tài)的組織型通訊膜系統(tǒng)，帶細胞分裂和通道狀態(tài)的細胞型識別通訊膜系統(tǒng)，以及帶細胞分裂和通道狀態(tài)的組織型通訊膜系統(tǒng). 對于這些膜系統(tǒng)，它們具有解決判定性問題的能力，本文分析了這些模型的計算能力和計算復雜性. 至今為止，膜計算作為自然計算中的一個分支，仍然是一個冉冉新生的計算模型，對于帶通道狀態(tài)的通訊膜系統(tǒng)來說，存在如下待解決的問題，且這些問題值得思考，具體如下.

(1)以串行方式工作的帶通道狀態(tài)，使用同向/異向規(guī)則的細胞型P系統(tǒng)已經(jīng)在文獻[52]中得以研究；以扁平極大并行方式工作，帶有通道狀態(tài)的通訊P 系統(tǒng)的通用性也得到了研究，在這項工作中同時獲得了NP完全問題的一個解. 然而值得關(guān)注的是在一些其他的操作策略中，如異步模式，無時間模式[62-64]，或者集合推導模式[65]下帶有細胞分裂和通道狀態(tài)的P系統(tǒng)的計算能力或者計算效率.

(2)可以將膜分離(或裂變)作為一種生物現(xiàn)象納入P系統(tǒng)中，它能夠在多項式時間內(nèi)產(chǎn)生大量的新細胞為計算提供一個指數(shù)級的工作空間，因此，有膜分離的各種形式的P系統(tǒng)可以解決NP完全問題[66-67]. 在文獻[68]中，HPP問題可以由工作在極大并行模式，有活性膜和分離規(guī)則的P系統(tǒng)解決，然而，HPP 問題是否能由帶細胞分離和通道狀態(tài)的通訊P系統(tǒng)來解決值得思考.

(3)由于PSPACE問題，如QSAT問題可以由帶有非基本膜分裂，使用通訊規(guī)則(同向/異向規(guī)則)的P系統(tǒng)高效地解決[30]. 因此，假設(shè)帶有非基本膜分裂和通道狀態(tài)的通訊P 系統(tǒng)也可以解決PSPACE問題，而如何解決仍然有待于思考.

(4)對于帶通道狀態(tài)的組織型通訊P系統(tǒng)來說，研究其工作在扁平極大并行模式下，且使用細胞分離規(guī)則的系統(tǒng)的計算能力和計算復雜性是一個有待于被解決的問題；

(5)依據(jù)各種生物活動特性，研究者們提出了串行模式、極小并行模式、極大并行模式以及扁平極大并行模式. 對于帶有通道狀態(tài)的通訊P系統(tǒng)來說，分別研究其在不同模式下的計算能力和計算復雜性是一個有待于解決的問題.