Abstract.
A new class of distributed computing models inspired from biology, that of P systems, was recently introduced by Gh. Paun. Several variants of P systems were already shown to be computationally universal, equal in power to Turing Machines. In this paper, we propose a class of P systems with active membranes where a membrane can be divided into an arbitrary (but finite) number of membranes. We prove that this variant is able to solve NP-complete problems in polynomial (in fact, linear) time. We exemplify this assertion with the well known Hamiltonian Path Problem and the Node Cover Decision Problem for undirected graphs.