The usefulness of P systems with membrane creation for solving
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
-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
-problem in linear time.