Warning: strtotime(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /var/www/html/www_publications/index.php on line 342

Warning: Cannot modify header information - headers already sent by (output started at /var/www/html/www_publications/index.php:342) in /var/www/html/www_publications/index.php on line 4076
Uniform Solutions to SAT and 3-SAT by Spiking Neural P Systems with Pre-computed Resources (bibtex)
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},
}