Ponencia
A Linear Solution for Subset Sum Problem with Tissue P Systems with Cell Division
Autor/es | Díaz Pernil, Daniel
Gutiérrez Naranjo, Miguel Ángel Pérez Jiménez, Mario de Jesús Riscos Núñez, Agustín |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2007 |
Fecha de depósito | 2016-03-15 |
Publicado en |
|
ISBN/ISSN | 9788461167760 |
Resumen | Tissue P systems are a computing model in the framework of Membrane
Computing where the tree-like membrane structure is replaced by a general graph. Recently,
it has been shown that endowing these P systems with cell ... Tissue P systems are a computing model in the framework of Membrane Computing where the tree-like membrane structure is replaced by a general graph. Recently, it has been shown that endowing these P systems with cell division, NP-complete problems can be solved in polynomial time. In this paper we present a solution to the Subset Sum problem via a family of such devices, and we also include the formal verification of such solution. This is the first solution to a numerical NP-complete problem by using tissue P systems with cell division. |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España Junta de Andalucía |
Identificador del proyecto | TIN2006-13425
TIC-581 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
subsetsuMiguel.pdf | 214.6Kb | [PDF] | Ver/ | |