Computational Complexity Theory in Membrane Computing

Speaker: Mario J. Pérez Jiménez (Universidad de Sevilla)

Mario J. Pérez Jiménez has been recently appointed as a member of Academia Europaea (The Academy of Europe). In his appointment discourse, he introduced the problem of approaching Membrane Computing models from a Computational Complexity point of view. The abstract is presented below.

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 models). 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 other higher 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 ≠ NP conjecture within the framework of this bio-inspired and non-conventional computing model are studied.

Information:

Date: Thursday, 11th of October 2012.
Time: 11:00
Place: Salón de Grados E.T.S. Ingeniería Informática
Language: Spanish