dc.creator | Valencia Cabrera, Luis | es |
dc.creator | Orellana Martín, David | es |
dc.creator | Martínez del Amor, Miguel Ángel | es |
dc.creator | Riscos Núñez, Agustín | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.date.accessioned | 2019-04-08T11:28:19Z | |
dc.date.available | 2019-04-08T11:28:19Z | |
dc.date.issued | 2017 | |
dc.identifier.citation | 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. | |
dc.identifier.issn | 0304-3975 | es |
dc.identifier.uri | https://hdl.handle.net/11441/85336 | |
dc.description.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. | es |
dc.description.sponsorship | National Natural Science Foundation of China No 61472328 | es |
dc.description.sponsorship | National Natural Science Foundation of China No 61320106005 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Theoretical Computer Science, 701 (november 2017), 226-234. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Membrane Computing | es |
dc.subject | Active membranes | es |
dc.subject | Cooperative rules | es |
dc.subject | Minimal cooperation | es |
dc.subject | Computational complexity | es |
dc.subject | the P versus NP problem | es |
dc.title | Reaching efficiency through collaboration in membrane systems: Dissolution, polarization and cooperation | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.relation.projectID | 61472328 | es |
dc.relation.projectID | 61320106005 | es |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0304397517304589 | es |
dc.identifier.doi | 10.1016/j.tcs.2017.04.015 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 9 | es |
dc.journaltitle | Theoretical Computer Science | es |
dc.publication.volumen | 701 | es |
dc.publication.issue | november 2017 | es |
dc.publication.initialPage | 226 | es |
dc.publication.endPage | 234 | es |