Solving the Partition Problem by Using Tissue-like P Systems with Cell Division

Abstract

Tissue-like P systems with cell division is a computing model in the framework of Membrane Computing that shares with the spiking neural P system model a similar biological inspiration. Namely, both models are based on the intercellular communication and cooperation between neurons, respectively. Due to this fact, in both models the devices have the same structure: a network of elementary units (cells in a tissue and interconnected neurons, respectively). Nonetheless, the two models are quite different. One of the differences is the ability of tissue-like P systems with cell division for increasing the number of cells during the computation. In this paper we exploit this ability and present a polynomial-time solution for the (NP-complete) Partition problem via a uniform family of such P systems.