1、作為自然計(jì)算的新領(lǐng)域,膜計(jì)算的目的是從生物細(xì)胞的結(jié)構(gòu)和功能的模擬中,創(chuàng)建一種分布式并行計(jì)算模型,使得該模型具有良好的計(jì)算性能。自膜計(jì)算提出以后,研究者們已經(jīng)證明膜計(jì)算模型不但具有與圖靈機(jī)一樣強(qiáng)大的計(jì)算能力,而且能有效地解決許多計(jì)算困難問題,如NP完全問題。2003年,膜計(jì)算被美國科學(xué)情報(bào)檢索機(jī)構(gòu)列為計(jì)算科學(xué)中快速發(fā)展的前沿領(lǐng)域。
　　本文通過使用帶有膜創(chuàng)生規(guī)則的膜系統(tǒng)這一計(jì)算模型,給出了3-SAT問題的多項(xiàng)式時(shí)間求解方法,然后在此

2、基礎(chǔ)上給出了3-SAT問題的與時(shí)間無關(guān)的求解方法,最后得到了SAT問題的與時(shí)間無關(guān)的求解方法。本文給出的3-SAT及SAT問題的求解方法,是通過膜創(chuàng)生規(guī)則,在線性時(shí)間內(nèi),產(chǎn)生指數(shù)量級的膜,并且每一個(gè)膜對應(yīng)與一個(gè)布爾變量的賦值,然后對每一個(gè)真值指派在相應(yīng)的膜內(nèi)進(jìn)行檢驗(yàn),最后綜合各個(gè)真值指派的檢驗(yàn)結(jié)果,判斷出3-SAT或SAT問題是否可滿足。
　　本文是首次在與時(shí)間無關(guān)的條件下,利用膜創(chuàng)生膜系統(tǒng)這一計(jì)算模型實(shí)現(xiàn)對3-SAT和SAT問題