Uniform Solutionto QAST Problem by Communication P Systems with Membrane Division and Promoters
Published in Computer Science, 2020
Abstract
Membrane computing is a branch of natural computing and all the computing models investigated in membrane compu-ting are called membrane systems. Communication in cells is a significant characteristic of membrane systems.Communication Psystems with membrane division are distributed parallel computing models, which can solve hard computational problems in poly-nomial 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 beguided by a promoter in one steprand 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-completeproblem QSAT by using symport rules of length at most 2 and promoters of length at most 1 in a polynomial time.