Research Group on Natural Computing

It is well known that the calculation speed of electronic processors has an upper bound which is clearly insufficient to efficiently solve instances whose size is relatively large associated with problems which model relevant real-life problems. In the last few decades, several computational paradigms inspired from nature have been developed with the aim of overcoming the barrier previously mentioned by using devices of the new computing models. For this purpose, the space–time trade-off method is used to develop efficient solutions to computationally hard problems. According to this, implementation of such models (in biological or any other substrate different from the electronic one) would provide a significant advance in the practical resolution of many real-life problems. Membrane computing is a computational paradigm motivated by the structure and functioning of the living cells, as well as from the organization of cells in tissues, organs, and other higher order structures. In this chapter, a computational complexity theory within the framework of Membrane Computing is introduced and the most relevant results obtained so far are presented.