Solving numerical NP-complete problems by spiking neural P systems with pre-computed resources

TitleSolving numerical NP-complete problems by spiking neural P systems with pre-computed resources
Publication TypeConference Contributions
Year of Publication2008
AuthorsGutiérrez-Naranjo, M. A., & Leporati A.
Conference Name6th Brainstorming Week on Membrane Computing
Volume TitleProceedings of the Sixth Brainstorming Week on Membrane Computing
ISBN Number978-84-612-44
PublisherFénix Editora
Place PublishedSevilla, Spain
Volume6
Pages193-210
Abstract

Recently we have considered the possibility of using spiking neural P systems
for solving computationally hard problems, under the assumption that some (possibly exponentially
large) pre-computed resources are given in advance. In this paper we continue
this research line, and we investigate the possibility of solving numerical NP-complete
problems such as Subset Sum. In particular, we first propose a semi–uniform family of
spiking neural P systems in which every system solves a specified instance of Subset
Sum. Then, we exploit a technique used to calculate Iterated Addition with boolean
circuits to obtain a uniform family of spiking neural P systems in which every system
is able to solve all the instances of Subset Sum of a fixed size. All the systems here
considered are deterministic, but their size generally grows exponentially with respect to
the instance size.

URLhttp://www.gcn.us.es/6BWMC/volume/subsetsum.pdf