基于膜創(chuàng)生膜系統(tǒng)的3-SAT及AT問(wèn)題求解方法.pdf

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

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