We consider 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 particular, we propose two uniform families of spiking neural P systems which can be used to address the NP-complete problems sat and 3-sat, respectively. Each system in the first family is able to solve all the instances of sat which can be built using n Boolean variables and m clauses, in a time which is quadratic in n and linear in m. Similarly, each system of the second family is able to solve all the instances of 3-sat that contain n Boolean variables, in a time which is cubic in n. All the systems here considered are deterministic.

Ishdorj, T., Leporati, A. (2008). Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre–computed resources. NATURAL COMPUTING, 7(4), 519-534 [10.1007/s11047-008-9081-0].

Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre–computed resources

LEPORATI, ALBERTO OTTAVIO
2008

Abstract

We consider 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 particular, we propose two uniform families of spiking neural P systems which can be used to address the NP-complete problems sat and 3-sat, respectively. Each system in the first family is able to solve all the instances of sat which can be built using n Boolean variables and m clauses, in a time which is quadratic in n and linear in m. Similarly, each system of the second family is able to solve all the instances of 3-sat that contain n Boolean variables, in a time which is cubic in n. All the systems here considered are deterministic.
Articolo in rivista - Articolo scientifico
Membrane computing - Pre-computed resources - SAT - 3-SAT - Spiking neural P systems
English
2008
7
4
519
534
none
Ishdorj, T., Leporati, A. (2008). Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre–computed resources. NATURAL COMPUTING, 7(4), 519-534 [10.1007/s11047-008-9081-0].
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/13137
Citazioni
  • Scopus 32
  • ???jsp.display-item.citation.isi??? ND
Social impact