dc.creator | Díaz Pernil, Daniel | |
dc.creator | Alhazov, Artiom | |
dc.creator | Freund, Rudolf | |
dc.creator | Gutiérrez Naranjo, Miguel Ángel | |
dc.date.accessioned | 2016-01-21T10:40:50Z | |
dc.date.available | 2016-01-21T10:40:50Z | |
dc.date.issued | 2015 | |
dc.identifier.isbn | 978-84-944366-2-8 | es |
dc.identifier.uri | http://hdl.handle.net/11441/33032 | |
dc.description.abstract | The set of NP-complete problems is split into weakly and strongly NP-
complete ones. The di erence consists in the in
uence of the encoding scheme of the
input. In the case of weakly NP-complete problems, the intractability depends on the
encoding scheme, whereas in the case of strongly NP-complete problems the problem
is intractable even if all data are encoded in a unary way. The reference for strongly
NP-complete problems is the Satis ability Problem (the SAT problem). In this paper,
we provide a uniform family of P systems with active membranes which solves SAT {
without polarizations, without dissolution, with division for elementary membranes and
with matter/antimatter annihilation. To the best of our knowledge, it is the rst solution
to a strongly NP-complete problem in this P system model. | es |
dc.description.sponsorship | Ministerio de Economía y Competitividad TIN2012-37434 | |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Fénix Editora | es |
dc.relation.ispartof | Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, 121-130. Sevilla, E.T.S. de Ingeniería Informática, 2-6 de Febrero, 2015, | es |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Solving SAT with Antimatter in Membrane Computing | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | |
dc.relation.projectID | info:eu-repo/grantAgreement/MINECO/TIN2012-37434 | |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | |
dc.contributor.group | Universidad de Sevilla. FQM296: Topología Computacional y Matemática Aplicada | |
dc.identifier.idus | https://idus.us.es/xmlui/handle/11441/33032 | |
dc.contributor.funder | Ministerio de Economía y Competitividad (MINECO). España | |