Published January 28, 2016
| Version v1
Publication
Antimatter as a Frontier of Tractability in Membrane Computing
Contributors
Others:
- Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
- Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
- Universidad de Sevilla. TIC193: Computación Natural
- Universidad de Sevilla. FQM296: Topología Computacional y Matemática Aplicada
- Ministerio de Economía y Competitividad (MINECO). España
Description
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.
Abstract
Ministerio de Economía y Competitividad TIN2012-37434Additional details
Identifiers
- URL
- https://idus.us.es/handle/11441/33487
- URN
- urn:oai:idus.us.es:11441/33487