带膜分裂和促进剂的通讯膜系统求解QSAT问题

摘要：

膜计算是自然计算的一个分支,膜计算中所研究的模型均称为膜系统,而细胞间通讯是膜系统的一个重要特征.带膜分裂的通讯膜系统是一种分布式并行计算模型,可以在多项式时间内解决计算困难问题.文中将促进剂引入带膜分裂的类细胞型通讯膜系统,提出了膜系统的一种变型——带膜分裂和促进剂的通讯膜系统,其中,一个促进剂可以同时控制多条规则,而促进剂本身不参与该条规则的进化.文中研究了带膜分裂和促进剂的通讯膜系统的计算效率,证明该类膜系统在使用同向规则长度为2,每条规则中促进剂的个数最多为1时,可以在多项式时间内求解PSPACE完全问题(QSAT问题)的统一解.

关键词：膜计算、细胞型P系统、同向/反向规则、QSAT问题

所属期刊栏目：47

资助基金：国家自然科学基金;中央高校基本科研业务费

在线出版日期：2020-05-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：38-42