Computing with membranes:: P systems with Worm-Objects

We consider a combination of P systems with objects described by symbols with P systems with objects described by strings. Namely we work with multisets of strings and consider as the result of a computation the number of strings in a given output membrane. The strings (also called worms) are processed by replication, splitting, mutation, and recombination; no priority among rules and no other ingredient is used. In these circumstances, it is proved that (1) P systems of this type can generate all recursively enumerable sets of numbers, and, moreover, (2) the Hamiltonian Path Problem in a directed graph can be solved in a quadratic time, while the SAT problem can be solved in a linear time. The interest of the latter result comes from the fact that it is the first time when a polynomial solution to an NP-complete problem is obtained in the P system framework without making use of the (non-realistic) operation of membrane division.