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