A linear solution for QSAT with membrane creation

The usefulness of P systems with membrane creation for solving NP problems has been previously proved (see [2,3]), but, up to now, it was an open problem whether such P systems were able to solve PSPACE-complete problems in polynomial time. In this paper we give an answer to this question by presenting a uniform family of P system with membrane creation which solves the QSAT-problem in linear time.