時間膜計算系統(tǒng)的計算性能研究.pdf

1、自然計算是觀察自然界中各種生物現象所抽象出來的一個研究領域。近年來，受生物細胞結構和功能的啟發(fā)，提出了一種新型的分布式生物計算模型—膜計算。在膜計算領域中研究的所有計算模型都統(tǒng)稱為膜系統(tǒng)。
　　在標準膜計算系統(tǒng)中，假設存在一個全局時鐘對系統(tǒng)中所有的區(qū)域進行計時，并且每條規(guī)則的執(zhí)行時間都是一個單位時間。然而，在活細胞中，化學反應或者復雜的生物操作（細胞分裂、細胞分離等）都需要一定的時間來執(zhí)行完成；在很多情況下，不同的生物過程需要花不

2、同的時間來完成，這些反應依賴于環(huán)境，催化劑等因素。因此，標準膜計算系統(tǒng)中每條規(guī)則執(zhí)行時間都是一個單位時間的假設是不合理的。基于這個生物實際，本文建立了能夠克服規(guī)則執(zhí)行時間長短的魯棒系統(tǒng)，提出了各種時間膜計算系統(tǒng)，研究了這些系統(tǒng)在時間無關模式下求解計算困難問題的能力以及產生數的能力。主要工作包括：
　　研究了帶時間的活性膜膜系統(tǒng)的計算能力，證明了在使用標準分裂規(guī)則（分裂生成的新膜標簽與它們的父代膜標簽相同）且分裂基本膜的情況下，活性

3、膜膜系統(tǒng)可以解決可滿足性（簡稱SAT）問題的時間無關半統(tǒng)一解（一個膜系統(tǒng)只能解決某個具體的例子）。如果系統(tǒng)允許分裂非基本膜，那么該膜系統(tǒng)可以解決SAT問題的時間無關統(tǒng)一解（一個膜系統(tǒng)可以解決一族參數大小相同的例子）。另外，給出了PSPACE完全問題（QSAT）的時間無關半統(tǒng)一解。最后，證明了時間無關活性膜膜系統(tǒng)在不同規(guī)則類型組合下都具有計算通用性。
　　提出了膜上帶蛋白的時間膜系統(tǒng)。研究了膜上帶蛋白的時間膜系統(tǒng)的計算能力，給出了基

4、于膜上帶蛋白膜系統(tǒng)的SAT問題時間無關統(tǒng)一解。證明了在時間無關模式下，該模型可以求解QSAT問題的統(tǒng)一解。本文還證明了時間無關膜上帶蛋白膜系統(tǒng)是計算通用的。
　　提出了膜生成的時間膜系統(tǒng)，研究了膜產生的時間膜系統(tǒng)的計算能力，證明了在時間無關模式下，如果考慮每個膜上都帶有一個電荷（或者正電荷或者負電荷或者中性），那么膜產生膜系統(tǒng)可以求解SAT問題的半統(tǒng)一解。另外，通過模擬帶出現檢測的矩陣文法，證明時間無關無極性膜產生膜系統(tǒng)（每個蛋白

5、質最多只有兩種狀態(tài)）是計算通用的。
　　考慮將時間概念引入到類組織膜系統(tǒng)中，提出了時間組織膜系統(tǒng)。我們研究帶細胞分裂的時間組織膜系統(tǒng)，證明了在時間無關模式下，該模型可以求解子集和問題。本文還證明了時間無關組織膜系統(tǒng)在通訊規(guī)則長度不超過3時是計算通用的。
　　將膜分裂引入到通訊（同向/反向）膜系統(tǒng)中，提出了帶膜分裂的通訊膜系統(tǒng)。在標準膜系統(tǒng)模式下研究了帶膜分裂的通訊膜系統(tǒng)的計算復雜性問題。通訊規(guī)則的長度定義為在該規(guī)則中所含物質

6、數目的總和。本文證明了基于膜分裂的通訊膜系統(tǒng)可以解決P類問題如果所有通訊規(guī)則的長度不超過1；其次，如果所有通訊規(guī)則的長度不超過3，并且只能分裂基本膜的情況下，該膜系統(tǒng)可以在線性時間內求解NP問題（子集和）；最后，證明了當所有通訊規(guī)則長度不超過3且分裂規(guī)則可以是非基本膜時，該膜系統(tǒng)可以有效的求解PSPACE問題（QSAT）。因此，在帶膜分裂的通訊膜系統(tǒng)框架下，我們提供了一個界：從通訊規(guī)則的長度不超過1到通訊規(guī)則長度不超過3對應于從非效率到