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 | 2021-04-06T10:23:23Z | |
dc.date.available | 2021-04-06T10:23:23Z | |
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 Cellular Solution to Subset Sum Using Division of Non-elementary Membranes and Dissolution, with Time and Initial Resources Bounded by log k. En WMC 2007: 8th Workshop on Membrane Computing (301-315), Thessaloniki, Greece: SEERC, South-East European Research Centre. | |
dc.identifier.uri | https://hdl.handle.net/11441/106733 | |
dc.description.abstract | The aim of our paper is twofold. On one hand we prove the ability of polar-
izationless P systems with dissolution and with division rules for non-elementary mem-
branes 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 di®erent 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 ¯xed 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.format.extent | 15 | es |
dc.language.iso | eng | es |
dc.publisher | SEERC, South-East European Research Centre | es |
dc.relation.ispartof | WMC 2007: 8th Workshop on Membrane Computing (2007), pp. 301-315. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | A Cellular Solution to Subset Sum Using Division of Non-elementary Membranes and Dissolution, with Time and Initial Resources Bounded by log k | 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 | 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 | http://www.seerc.org/wmc8/procedings_web/PaperIndex.htm | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
dc.publication.initialPage | 301 | es |
dc.publication.endPage | 315 | es |
dc.eventtitle | WMC 2007: 8th Workshop on Membrane Computing | es |
dc.eventinstitution | Thessaloniki, Greece | es |
dc.relation.publicationplace | Thessaloniki, Greece | es |
dc.contributor.funder | Ministerio de Educación y Ciencia (MEC). España | es |
dc.contributor.funder | Junta de Andalucía | es |