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

The aim of this paper is to introduce to the reader the main ideas of compu ting with membranes, a recent branch of (theoretical) molecular computing. In short, in a cell-like system, multisets of objects evolve according to g iven rules in the compartments defined by a membrane structure and compute natural numbers as the result of halting sequences of transitions. The mode l is parallel, nondeterministic. Many variants have already been considered and many problems about them were investigated. We present here some of th ese variants, focusing on two central classes of results: (1) characterizat ions of the recursively enumerable: sets of numbers and (2) possibilities t o solve NP-complete problems in polynomial - even linear - time (of course. by making use of an exponential space). The results are given without proo fs. An almost complete bibliography of the domain, at the middle of October 2000. is also provided. (C) 2001 Elsevier Science Ireland Ltd. All rights reserved.