Solving a PSPACE-complete problem by symport/antiport P systems with promoters and membrane division

Symport/antiport P systems with membrane division are parallel computing models, which can solve NP-complete problems in polynomial time. In this paper, promoters are incorporated into symport/antiport P systems with membrane division, and a new kind of P systems, called symport/antiport P systems with promoters and membrane division (SAPD P systems, for short) is proposed. The computational efficiency of SAPD P systems is investigated. We show that a uniform solution to the QSAT problem is given by using only symport rules of length at most 2 and promoters of length at most 1 in a polynomial time (Note that the QSAT problem can be solved by symport/antiport P systems with membrane division using both symport rules and antiport rules of length at most 3 (Song et al. in BioSystems 130: 51–58, 2015)).