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.

Leporati, A., Gutierrez Naranjo, M. (2008). Solving Subset Sum by Spiking Neural P Systems with Pre–computed Resources. FUNDAMENTA INFORMATICAE, 87(1), 61-77.

Solving Subset Sum by Spiking Neural P Systems with Pre–computed Resources

LEPORATI, ALBERTO OTTAVIO;
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.
Articolo in rivista - Articolo scientifico
Membrane computing, NP-complete problems, Subset Sum, Spiking neural P systems
English
2008
87
1
61
77
none
Leporati, A., Gutierrez Naranjo, M. (2008). Solving Subset Sum by Spiking Neural P Systems with Pre–computed Resources. FUNDAMENTA INFORMATICAE, 87(1), 61-77.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/13139
Citazioni
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 21
Social impact