Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources

In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known -complete problems: and . In the case of , the answer to any instance of the problem is computed in a time which is linear with respect to both the number of Boolean variables and the number of clauses that compose the instance. As for , the answer is computed in a time which is at most cubic in the number of Boolean variables.