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

Uniform Solution to QAST Problem by Communication P Systems with Membrane Division and Promoters

作　　者：宋勃升 程玉 SONG Bo-sheng;CHENG Yu(College of Information Science and Engineering,Hunan University,Changsha 410082,China)

机构地区：[1]湖南大学信息科学与工程学院,长沙410082

出　　处：《计算机科学》2020年第5期38-42,共5页Computer Science

基　　金：国家自然科学基金(61972138,61602192);中央高校基本科研业务费(531118010355)。

摘　　要：膜计算是自然计算的一个分支,膜计算中所研究的模型均称为膜系统,而细胞间通讯是膜系统的一个重要特征。带膜分裂的通讯膜系统是一种分布式并行计算模型,可以在多项式时间内解决计算困难问题。文中将促进剂引入带膜分裂的类细胞型通讯膜系统,提出了膜系统的一种变型——带膜分裂和促进剂的通讯膜系统,其中,一个促进剂可以同时控制多条规则,而促进剂本身不参与该条规则的进化。文中研究了带膜分裂和促进剂的通讯膜系统的计算效率,证明该类膜系统在使用同向规则长度为2,每条规则中促进剂的个数最多为1时,可以在多项式时间内求解PSPACE完全问题(QSAT问题)的统一解。Membrane computing is a branch of natural computing,and all the computing models investigated in membrane computing are called membrane systems.Communication in cells is a significant characteristic of membrane systems.Communication P systems with membrane division are distributed parallel computing models,which can solve hard computational problems in polynomial time.In this work,promoters are introduced into communication P systems with membrane division,and a variant of P systems,called communication P systems with membrane division and promoters is proposed,where any number of rules can be guided by a promoter in one step,and promoters do not participate the evolution process when the evolved rules are used.The computational efficiency of this kind of P systems is studied.This paper presents a uniform solution to the PSPACE-complete problem QSAT by using symport rules of length at most 2 and promoters of length at most 1 in a polynomial time.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]