Presentation
Antimatter as a Frontier of Tractability in Membrane Computing
Author/s | Díaz Pernil, Daniel
Peña Cantillana, Francisco Gutiérrez Naranjo, Miguel Ángel |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2014 |
Deposit Date | 2016-01-28 |
Published in |
|
ISBN/ISSN | 978-84-940056-4-0 |
Abstract | 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. |
Funding agencies | Ministerio de Economía y Competitividad (MINECO). España |
Project ID. | info:eu-repo/grantAgreement/MINECO/TIN2012-37434 |
Files | Size | Format | View | Description |
---|---|---|---|---|
155_antimatter_tractability.pdf | 104.2Kb | [PDF] | View/ | |