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

• 作者: 宋勃升 程玉
• 来源期刊: 计算机科学
• 关键词: 膜计算 细胞型P系统 同向/反向规则 QSAT问题
• 年，卷（期）: 2020,（5）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 38-42
• 页数: 5页
• 字数: 5563字
• 语种: 中文
• DOI: 10.11896/jsjkx.191100204

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宋勃升	湖南大学信息科学与工程学院	2	0	0.0	0.0
2	程玉	湖南大学信息科学与工程学院	1	0	0.0	0.0