Uniform Solution to QSAT by P Systems with Proteins

P systems are distributed parallel computing models in the area of membrane computing, which are inspired by the structure and the functioning of living cells, as well as the organization of cells in tissues, organs, and other higher order structures. P systems with proteins on membranes are a class of P systems, which have proved to be very efficient computing devices. Specifically, it was known that the Quantified satisfiability problem (QSAT) of a Boolean formula can be solved by a semi-uniform family of P systems with proteins on membranes and with membrane division. However, it remains open whether a uniform families of P systems with proteins on membranes can solve in polynomial time exactly the class of problems PSPACE. In this work, we present a uniform solution to QSAT problem by P systems with proteins on membranes in a linear time with respect to both the number n of Boolean variables and the number m of clauses of the instance, which answers the above open problem.