Thu, 03/17/2016 - 17:20 — manu

Title | Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division |

Publication Type | Journal Papers |

Year of Publication | 2015 |

Authors | Song, B., Pérez-Jiménez M. J., & Pan L. |

Journal Title | Biosystems |

Publisher | Elsevier |

Place Published | San Diego, CA, USA |

Volume | 130 |

Pages | 51-58 |

Date Published | 04/2015 |

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

Keywords | Cell-like P system; Symport/Antiport rule; Membrane division; Subset Sum problem; QSAT problem |

URL | http://www.sciencedirect.com/science/article/pii/S0303264715000350 |

Impact Factor | 1.548 |

Ranking | 37/85 - Q2 |

ISSN Number | 0303-2647 |

DOI | 10.1016/j.biosystems.2015.03.002 |