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

A uniform solution to SAT using membrane creation


Advanced Search
Opened Access A uniform solution to SAT using membrane creation

Show item statistics
Export to
Author: Gutiérrez Naranjo, Miguel Ángel
Pérez Jiménez, Mario de Jesús
Romero Campero, Francisco José
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2007
Published in: Theoretical Computer Science, 371 (1-2), 54-61.
Document type: Article
Abstract: In living cells, new membranes are produced basically through two processes: mitosis and autopoiesis. These two processes have inspired two variants of cell-like membrane systems, namely P systems with active membranes and P systems with membrane creation. In this paper, we provide the first u niform, e fficient so lution to th e SAT pr oblem in th e fr amework of re cogniser P systems with membrane creation using dissolution rules. Recently the authors have proved that if the dissolution rules are not allowed to be used, then the polynomial complexity class associated with this variant of P systems is the standard complexity class P. This result, together with the main result of this paper, shows the surprising role of the apparently “innocent” operation of membrane dissolution. The use of this type of rule establishes the difference between efficiency and non-efficiency for P systems with membrane creation, and provides a barrier between P and NP (assuming P 6= NP).
Cite: Gutiérrez Naranjo, M.Á., Pérez Jiménez, M.d.J. y Romero Campero, F.J. (2007). A uniform solution to SAT using membrane creation. Theoretical Computer Science, 371 (1-2), 54-61.
Size: 298.2Kb
Format: PDF


DOI: 10.1016/j.tcs.2006.10.013

See editor´s version

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

This item appears in the following Collection(s)