Ponencia
Antimatter as a Frontier of Tractability in Membrane Computing
Autor/es | Díaz Pernil, Daniel
Peña Cantillana, Francisco Gutiérrez Naranjo, Miguel Ángel |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2014 |
Fecha de depósito | 2016-01-28 |
Publicado en |
|
ISBN/ISSN | 978-84-940056-4-0 |
Resumen | It is well known that the polynomial complexity class of recognizer polarizationless
P systems with active membranes, without dissolution and with division for
elementary and non-elementary membranes is exactly the ... It is well known that the polynomial complexity class of recognizer polarizationless P systems with active membranes, without dissolution and with division for elementary and non-elementary membranes is exactly the complexity class P (see [6], Th. 2). In this paper, we prove that if such P system model is endowed with antimatter and annihilation rules, then NP problems can be solved. In this way, antimatter is a frontier of tractability in Membrane Computing. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | info:eu-repo/grantAgreement/MINECO/TIN2012-37434 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
155_antimatter_tractability.pdf | 104.2Kb | [PDF] | Ver/ | |