%0 Generic
%D 2008
%T Solving numerical NP-complete problems by spiking neural P systems with pre-computed resources
%A Miguel A. Gutiérrez-Naranjo
%A Alberto Leporati
%C Sevilla, Spain
%I Fénix Editora
%P 193-210
%S Proceedings of the Sixth Brainstorming Week on Membrane Computing
%U http://www.gcn.us.es/6BWMC/volume/subsetsum.pdf
%V 6
%X 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.
%@ 978-84-612-44