A Linear Time Solution to the Partition Problem in a Cellular Tissue-Like Model

Abstract

Tissue-like P systems with cell division is a computing model in the framework of membrane computing that is based on the intercellular communication and cooperation between neurons. In such a model, the structure of the devices is a network of elementary cells. Tissue-like P systems with cell division have the ability of increasing the number of cells during the computation. In this paper we exploit this ability and present a polynomial-time (actually, linear-time) solution to the NP-complete Partition problem via a uniform family of such P systems.