Published January 28, 2016
| Version v1
Publication
Antimatter as a Frontier of Tractability in Membrane Computing
- 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-37434
Additional details
- URL
- https://idus.us.es/handle/11441/33487
- URN
- urn:oai:idus.us.es:11441/33487
- Origin repository
- USE