Artículo
Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division
Autor/es | Song, Bosheng
Pérez Jiménez, Mario de Jesús Pan, Linqiang |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2015 |
Fecha de depósito | 2021-05-20 |
Publicado en |
|
Resumen | P systems are computing models inspired by some basic features of biological membranes. In this work, membrane division, which provides a way to obtain an exponential workspace in linear time, is introduced into (cell-like) ... P systems are computing models inspired by some basic features of biological membranes. In this work, membrane division, which provides a way to obtain an exponential workspace in linear time, is introduced into (cell-like) P systems with communication (symport/antiport) rules, where objects are never modified but they just change their places. The computational efficiency of this kind of P systems is studied. Specifically, we present a (uniform) linear time solution to the NP-complete problem, Subset Sum by using division rules for elementary membranes and communication rules of length at most 3. We further prove that such P system allowing division rules for non-elementary membranes can efficiently solve the PSPACE-complete problem, QSAT in a uniform way. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | TIN2012-37434 |
Cita | Song, B., Pérez Jiménez, M.d.J. y Pan, L. (2015). Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division. BioSystems, 130 (april 2015), 51-58. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Efficient solutions to hard ... | 440.7Kb | [PDF] | Ver/ | |