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},
}
Powered by bibtexbrowser