Solving subset sum by spiking neural P systems with pre-computed resources

TitleSolving subset sum by spiking neural P systems with pre-computed resources
Publication TypeJournal Papers
Year of Publication2008
AuthorsLeporati, A., & Gutiérrez-Naranjo M. A.
Journal TitleFundamenta Informaticae
PublisherIOS Press
Place PublishedWarsaw, Poland
Volume87
Pages61-77
Date Published09/2008
Abstract

Recently the possibility of using spiking neural P systems for solving computationally hard problems has been considered. Such solutions assume that some (possibly exponentially large) pre-computed resources are given in advance, provided that their structure is "regular" and they do not contain neither "hidden information" that simplify the solution of specific instances, nor an encoding of all possible solutions (that is, an exponential amount of information that allows to cheat while solving the instances of the problem). 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 specific 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 any instance of SUBSET SUM of a fixed size. All the systems here considered are deterministic, and their size generally grows exponentially with respect to the instance size.

Issue1
Impact Factor

0.715

Ranking

102/175 - Q3

ISSN Number0169-2968