基于膜创生膜系统的3-SAT及AT问题求解方法

摘要

作为自然计算的新领域,膜计算的目的是从生物细胞的结构和功能的模拟中,创建一种分布式并行计算模型,使得该模型具有良好的计算性能。自膜计算提出以后,研究者们已经证明膜计算模型不但具有与图灵机一样强大的计算能力,而且能有效地解决许多计算困难问题,如NP完全问题。2003年,膜计算被美国科学情报检索机构列为计算科学中快速发展的前沿领域。
　　本文通过使用带有膜创生规则的膜系统这一计算模型,给出了3-SAT问题的多项式时间求解方法,然后在此基础上给出了3-SAT问题的与时间无关的求解方法,最后得到了SAT问题的与时间无关的求解方法。本文给出的3-SAT及SAT问题的求解方法,是通过膜创生规则,在线性时间内,产生指数量级的膜,并且每一个膜对应与一个布尔变量的赋值,然后对每一个真值指派在相应的膜内进行检验,最后综合各个真值指派的检验结果,判断出3-SAT或SAT问题是否可满足。
　　本文是首次在与时间无关的条件下,利用膜创生膜系统这一计算模型实现对3-SAT和SAT问题的求解。由于实际生物细胞中反应规则的执行很难满足同步条件,研究与时间无关的求解方法就很有意义。基于膜创生膜系统的3-SAT和SAT问题的解法是一种完备的求解方法,可以准确的判断出3-SAT及SAT问题的可满足性。此外,膜系统与生俱来的极大并行性保证了该求解方法的求解效率。

目录

封面

声明

中文摘要

英文摘要

目录

1 引言

1.1研究目的和意义

1.2国内外研究现状

1.3膜计算膜系统

1.4本文的创新之处

1.5研究内容与结构

2 膜创生膜系统模型的构建

2.1带膜溶解规则的膜系统

2.2带膜创生规则的膜系统

2.3带膜创生规则的识别膜系统

2.4 膜创生膜系统求解3-SAT和SAT问题的步骤

2.5本章小结

3基于膜创生膜系统的3-SAT问题的多项式时间解法

3.1多项式时间求解3-SAT问题的膜创生膜系统

3.2 3-SAT问题的多项式时间解法的计算过程

3.3 本章小结

4基于膜创生膜系统的3-SAT问题的与时间无关解法

4.1 与时间无关求解3-SAT问题的膜创生膜系统

4.2 3-SAT问题的与时间无关解法的计算过程

4.3 本章小结

5基于膜创生膜系统的SAT问题的与时间无关解法

5.1与时间无关求解SAT问题的膜创生膜系统

5.2 SAT问题的与时间无关解法的计算过程

5.3 本章小结

6总结与展望

6.1 全文总结

6.2 研究展望

致谢

参考文献

附录攻读学位期间发表的学术论文