Tue, 10/21/2008 - 10:12 — mmartinez

Title | Uniform solutions to SAT and Subset Sum by spiking neural P systems |

Publication Type | Journal Papers |

Year of Publication | 2009 |

Authors | Leporati, A., Mauri G., Zandron C., Paun G., & Pérez-Jiménez M. J. |

Journal Title | Natural Computing |

Publisher | Springer Verlag |

Place Published | Amsterdam, Netherlands |

Volume | 8 |

Pages | 681-702 |

Date Published | 12/2009 |

Abstract | We continue the investigations concerning the possibility of using spiking neural P systems as a framework for solving computationally hard problems, addressing two problems which were already recently considered in this respect: SubsetSum and SAT. For both of them we provide uniform constructions of standard spiking neural P systems (i.e., not using extended rules or parallel use of rules) which solve these problems in a constant number of steps, working in a non-deterministic way. This improves known results of this type where the construction was non-uniform, and/or was using various ingredients added to the initial definition of spiking neural P systems (the SN P systems as defined initially are called here “standard”). However, in the SubsetSum case, a price to pay for this improvement is that the solution is obtained either in a time which depends on the value of the numbers involved in the problem, or by using a system whose size depends on the same values, or again by using complicated regular expressions. A uniform solution to SAT is also provided, that works in constant time. |

Keywords | Membrane computing; Spiking neural P system; SAT problem; Subset sum problem; Complexity |

URL | http://dx.doi.org/10.1007/s11047-008-9091-y |

Issue | 4 |

ISSN Number | 1567-7818 |

DOI | 10.1007/s11047-008-9091-y |