Research Group on Natural Computing

Speaker: Prof. Mario J. Pérez-Jiménez
University of Seville (Spain)
Member of the Academia Europaea (The Academy of Europe)

SEMINAR

Title: Attacking the P versus NP problem: seeking sharper frontiers of the efficiency in Tissue P systems

Abstract: 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 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 presented.

Information:

• Date: Thursday, 05-12-2013
• Time: 11:45 - 13:30.
• Place: Seminar room of IMUS (First floor, Edificio Celestino Mutis)
• Language: English

Organized by:

• Research Group on Natural Computing
• Institute of Mathematics of the University of Seville (Instituto de Matemáticas de la Universidad de Sevilla)