Solving the SAT problem using spiking neural P systems with structural plasticity and pre-computed resources

Abstract In this paper, we use generalized spiking neural P systems model with structural plasticity (SNPSP) for solving the SAT problem. It is an interesting variant of the spiking neural P systems (SNPS) model. In generalized SNPS with structural plasticity models, more than one synaptic connection can be established between two neurons using plasticity rules. The system proposed in the paper solves SAT problem in a deterministic and uniform manner. More specifically, the solution belongs to the category of EXP-uniform, i.e., the initial configuration of the system, a deterministic Turing machine cannot use less than an exponential number of computational steps. The time required to solve SAT problem is linear in n and m where n and m are the numbers of variables and clauses respectively. Our work is the first solution to use pre-computed resources with structural dynamism, that is plasticity rules in this case, to solve the SAT problem. Also, no delay is associated with the rules of the SNPS system proposed in this paper.