Computational Complexity Theory in Membrane Computing#

Mario de J. Perez Jimenez
#

Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence
University of Sevilla
marper@us.es

Abstract

In the last decades several computing models using powerful tools from Nature have been developed (because of this, they are known as bio-inspired mod- els). Commonly, the space-time tradeoff method is used to develop efficient solutions to computationally hard problems. According to this, implementation of such models (in biological, electronic, or any other substrate) would provide a signifcant advance in the practical resolution of hard problems.

Membrane computing is a young branch of natural computing initiated by Gh. Paun at the end of 1998. It is inspired by the structure and functioning of living cell, as well as from the organization of cells in tissues, organs, and otherhigher order structures.

The devices of this paradigm, called P systems or membrane systems, constitute models for distributed, parallel and non-deterministic computing.

In this talk, a computational complexity theory within the framework of Membrane Computing is introduced.

Polynomial complexity classes associated with different models of cell-like and tissue-like membrane systems are defined and the most relevant results obtained so far are presented. Different borderlines between efficiency and non-effciency are shown, and many attractive characterizations of the P 6= NP conjecture within the framework of this bio-inspired and non-conventional computing model are studied.