dc.creator | Díaz Pernil, Daniel | es |
dc.creator | Gutiérrez Naranjo, Miguel Ángel | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.creator | Riscos Núñez, Agustín | es |
dc.date.accessioned | 2017-04-06T09:02:10Z | |
dc.date.available | 2017-04-06T09:02:10Z | |
dc.date.issued | 2007 | |
dc.identifier.citation | Díaz Pernil, D., Gutiérrez Naranjo, M.Á., Pérez Jiménez, M.d.J. y Riscos Núñez, A. (2007). A Logarithmic Bound for Solving Subset Sum with P Systems. En WMC 2007: International Workshop on Membrane Computing (257-270), Tesalonica, Grecia: Springer. | |
dc.identifier.isbn | 978-3-540-77311-5 | es |
dc.identifier.issn | 0302-9743 | es |
dc.identifier.uri | http://hdl.handle.net/11441/57252 | |
dc.description.abstract | The aim of our paper is twofold. On one hand we prove the
ability of polarizationless P systems with dissolution and with division
rules for non-elementary membranes to solve NP-complete problems in
a polynomial number of steps, and we do this by presenting a solution to
the Subset Sum problem. On the other hand, we improve some similar
results obtained for different models of P systems by reducing the number
of steps and the necessary resources to be of a logarithmic order with
respect to k (recall that n and k are the two parameters used to indicate
the size of an instance of the Subset Sum problem).
As the model we work with does not allow cooperative rules and
does not consider the membranes to have an associated polarization,
the strategy that we will follow consists on using objects to represent
the weights of the subsets through their multiplicities, and comparing the
number of objects against a fixed number of membranes. More precisely,
we will generate k membranes in log k steps. | es |
dc.description.sponsorship | Ministerio de Educación y Ciencia TIN2006-13425 | es |
dc.description.sponsorship | Junta de Andalucía TIC-581 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Springer | es |
dc.relation.ispartof | WMC 2007: International Workshop on Membrane Computing (2007), p 257-270 | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | A Logarithmic Bound for Solving Subset Sum with P Systems | es |
dc.type | info:eu-repo/semantics/conferenceObject | 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 | TIN2006–13425 | es |
dc.relation.projectID | TIC-581 | es |
dc.relation.publisherversion | https://link.springer.com/chapter/10.1007%2F978-3-540-77312-2_16 | es |
dc.identifier.doi | 10.1007/978-3-540-77312-2_16 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 14 | es |
dc.publication.initialPage | 257 | es |
dc.publication.endPage | 270 | es |
dc.eventtitle | WMC 2007: International Workshop on Membrane Computing | es |
dc.eventinstitution | Tesalonica, Grecia | es |
dc.relation.publicationplace | Berlin | es |
dc.contributor.funder | Ministerio de Educación y Ciencia (MEC). España | |
dc.contributor.funder | Junta de Andalucía | |