Mon, 10/27/2008 - 14:40 — mmartinez

Title | A logarithmic bound for solving Subset Sum with P systems |

Publication Type | Journal Papers |

Year of Publication | 2007 |

Authors | Díaz-Pernil, D., Gutiérrez-Naranjo M. A., Pérez-Jiménez M. J., & Riscos-Núñez A. |

Journal Title | Lecture Notes in Computer Science |

ISBN Number | 978-3-540-77311-5 |

Publisher | Springer |

Place Published | Amsterdam, The Netherlands |

Pages | 257-270 |

Date Published | June 25-28, 2007 |

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). |

URL | http://www.springerlink.com/content/tq37h93l8p454153/ |

Notes | In G. Elefterakis, P. Kefalas, Gh. Paun, G. Rozenberg, A. Salomaa (eds.) |

ISSN Number | 0302-9743 |

DOI | 10.1007/978-3-540-77312-2_16 |