dc.creator | Gutiérrez Naranjo, Miguel Ángel | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.creator | Romero Campero, Francisco José | es |
dc.date.accessioned | 2017-12-22T10:46:28Z | |
dc.date.available | 2017-12-22T10:46:28Z | |
dc.date.issued | 2007 | |
dc.identifier.citation | 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. | |
dc.identifier.issn | 0304-3975 | es |
dc.identifier.uri | http://hdl.handle.net/11441/67988 | |
dc.description.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). | es |
dc.description.sponsorship | Ministerio de Ciencia y Tecnología TIC2002-04220-C03-01 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Theoretical Computer Science, 371 (1-2), 54-61. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Natural computing | es |
dc.subject | Membrane Computing | es |
dc.subject | Cellular complexity classes | es |
dc.subject | SAT problem | es |
dc.title | A uniform solution to SAT using membrane creation | 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 | TIC2002-04220-C03-01 | es |
dc.relation.publisherversion | http://www.sciencedirect.com/science/article/pii/S0304397506007651?via%3Dihub | es |
dc.identifier.doi | 10.1016/j.tcs.2006.10.013 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 8 | es |
dc.journaltitle | Theoretical Computer Science | es |
dc.publication.volumen | 371 | es |
dc.publication.issue | 1-2 | es |
dc.publication.initialPage | 54 | es |
dc.publication.endPage | 61 | es |
dc.identifier.sisius | 6651353 | es |
dc.contributor.funder | Ministerio de Ciencia y Tecnología (MCYT). España | |