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

Reaching efficiency through collaboration in membrane systems: Dissolution, polarization and cooperation

 

Advanced Search
 
Acceso restringido Reaching efficiency through collaboration in membrane systems: Dissolution, polarization and cooperation
Cites

Show item statistics
Icon
Export to
Author: Valencia Cabrera, Luis
Orellana Martín, David
Martínez del Amor, Miguel Ángel
Riscos Núñez, Agustín
Pérez Jiménez, Mario de Jesús
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2017
Published in: Theoretical Computer Science, 701 (november 2017), 226-234.
Document type: Article
Abstract: From a computational complexity point of view, some syntactical ingredients play differentroles depending on the kind of combination considered. Inspired by the fact that the passing of a chemical substance through a biological membrane is often done by an interaction with the membrane itself, systems with active membranes were considered.Several combinations of different ingredients have been used in order to know which kindof problems could they solve efficientlyIn this paper, minimal cooperation with a minimal expression (the left-hand side of every object evolution rule has at most two objects and its right-hand side contains only one object) in object evolution rules is considered and a polynomial-time uniform solution to the SAT problem is presented. Consequently, a new way to tackle the P versus NP problem is provided.
Cite: Valencia Cabrera, L., Orellana Martín, D., Martínez del Amor, M.Á., Riscos Núñez, A. y Pérez Jiménez, M.d.J. (2017). Reaching efficiency through collaboration in membrane systems: Dissolution, polarization and cooperation. Theoretical Computer Science, 701 (november 2017), 226-234.
Size: 508.0Kb
Format: PDF
xmlui.item.no_texto_completo  until  2019-11.  For more information contact idus@us.es

URI: https://hdl.handle.net/11441/85336

DOI: 10.1016/j.tcs.2017.04.015

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)