Uniform Solutions to SAT and 3-SAT by Spiking Neural P Systems with Pre-computed Resources (bibtex)
by Ishdorj, Tseren-Onolt and Leporati, Alberto
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.
Reference:
Uniform Solutions to SAT and 3-SAT by Spiking Neural P Systems with Pre-computed Resources (Ishdorj, Tseren-Onolt and Leporati, Alberto), In Natural Computing, Springer, volume 7, 2008.
Bibtex Entry:
@Article{j177,
author    = {Ishdorj, Tseren-Onolt AND Leporati, Alberto},
title     = {Uniform Solutions to SAT and 3-SAT by Spiking Neural P Systems with Pre-computed Resources},
journal   = {Natural Computing},
year      = {2008},
volume    = {7},
number    = {4},
pages     = {519--534},
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. },
keywords  = {computational efficiency, pre-computet resources},
pdf       = {pdfs/IL2008c.pdf},
publisher = {Springer},
}