Repositorio de producción científica de la Universidad de Sevilla

Antimatter as a Frontier of Tractability in Membrane Computing


Advanced Search
Opened Access Antimatter as a Frontier of Tractability in Membrane Computing
Show item statistics
Export to
Author: 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)
Date: 2014
Published in: Proceedings of the Twelfth Brainstorming Week on Membrane Computing, 155-168. Sevilla, E.T.S. de Ingeniería Informática, 3-7 de Febrero, 2014.
ISBN/ISSN: 978-84-940056-4-0
Document type: Presentation
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 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.
Size: 104.2Kb
Format: PDF


This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 InternacionalAttribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)