View source for Membrane Computing

==Power and Efficiency==
From a theoretical point of view, P systems are both:

''powerful'' as most classes of P systems are Turing complete, even when using ingredients of a reduced complexity - a small number of membranes, rules of simple forms, ways of controlling the use of rules directly inspired from biology are sufficient for generating/accepting all sets of numbers or languages generated by Turing machines; also small universal P systems of various types were produced, and 

''efficient'', as many classes of P systems, especially those with enhanced parallelism, can solve computationally hard problems - typically '''NP'''-complete problems, but also harder problems, e.g., '''PSPACE'''-complete problems - in a feasible time - typically polynomial). Such a speed-up is
obtained by trading space for time, with the space grown exponentially in a linear time by means of bio-inspired operations.
The most investigated way to obtain such an exponential workspace is membrane division [[#10|P&#x0103;un Gh. (2001)]], but also membrane creation, membrane separation,
string replication and other operations were used. These operations were then extended to cells in tissue-like P systems and even to
neurons in SN P systems - and in all cases similar results were obtained: polynomial time solutions to computationally hard problems.
Details can be found, e.g., in [[#11|Perez-Jimenez M.J. (2009)]] and [[computational complexity in P systems]].