Affiliations: Dipartimento di Informatica, Sistemistica e
Comunicazione Università, degli Studi di Milano - Bicocca, Viale Sarca
336/14, 20126 Milano, Italy. alberto.leporati@unimib.it | Department of Computer Science and Artificial
Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla,
Spain. magutier@us.es
Note: [] Address for corresponding: Dipartimento di Informatica,
Sistemistica e Comunicazione, Università degli Studi di Milano –
Bicocca, Viale Sarca 336/14, 20126 Milano, Italy
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.
Keywords: Membrane computing, spiking neural P systems, NP-complete problems, Subset Sum
