<?xml version="1.0" encoding="UTF-8"?><xml><records><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Daniel Díaz-Pernil</style></author><author><style face="normal" font="default" size="100%">Miguel A. Gutiérrez-Naranjo</style></author><author><style face="normal" font="default" size="100%">Mario J. Pérez-Jiménez</style></author><author><style face="normal" font="default" size="100%">Agustín Riscos-Núñez</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">A logarithmic bound for solving Subset Sum with P systems</style></title><secondary-title><style face="normal" font="default" size="100%">Lecture Notes in Computer Science</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2007</style></year><pub-dates><date><style  face="normal" font="default" size="100%">June 25-28, 2007</style></date></pub-dates></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.springerlink.com/content/tq37h93l8p454153/</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Springer</style></publisher><pub-location><style face="normal" font="default" size="100%">Amsterdam, The Netherlands</style></pub-location><pages><style face="normal" font="default" size="100%">257-270</style></pages><isbn><style face="normal" font="default" size="100%">978-3-540-77311-5</style></isbn><abstract><style face="normal" font="default" size="100%">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 logk steps.</style></abstract><notes><style face="normal" font="default" size="100%">In G. Elefterakis, P. Kefalas, Gh. Paun, G. Rozenberg, A. Salomaa (eds.)
Revised, Selected, and Invited Papers. Lecture Notes in Computer Science, Springer-Verlag, Berlin-Heidelberg, 4860 (2007), 257-270</style></notes></record></records></xml>