Solving a PSPACE-Complete Problem by Recognizing P Systems with Restricted Active Membranes

Abstract

P systems are parallel molecular computing models based on processing multisets of objects in cell-like membrane structures. Recently, Petr Sosík has shown that a semi-uniform family of P systems with active membranes and 2-division is able to solve the PSPACE-complete problem QBF-SAT in linear time; he has also conjectured that the membrane dissolving rules of the (d) type may be omitted, but probably not the (f) type rules for non-elementary membrane division. In this paper, we partially confirm the conjecture proving that dissolving rules are not necessary. Moreover, the construction is now uniform. It still remains open whether or not non-elementary membrane division is needed.