From cells to computers: computing with membranes (P systems)

The aim of this paper is to introduce to the reader the main ideas of computing with membranes, a recent branch of (theoretical) molecular computing. In short, in a cell-like system, multisets of objects evolve according to given rules in the compartments defined by a membrane structure and compute natural numbers as the result of halting sequences of transitions. The model is parallel, nondeterministic. Many variants have already been considered and many problems about them were investigated. We present here some of these variants, focusing on two central classes of results: (1) characterizations of the recursively enumerable sets of numbers and (2) possibilities to solve NP-complete problems in polynomial--even linear--time (of course, by making use of an exponential space). The results are given without proofs. An almost complete bibliography of the domain, at the middle of October 2000, is also provided.