On the Computational Power of Spiking Neural P Systems
Alberto Leporati, Claudio Zandron, Claudio Ferretti and Giancarlo Mauri
We investigate some computational properties of spiking neural P systems. In particular, we first show that nondeterministic spiking neural P systems are able to solve (in a semi-uniform setting) the NP-complete problem 3-SAT in constant time. Then, we show how to simulate a universal deterministic spiking neural P system with a deterministic Turing machine, in a time which is polynomial with respect to the execution time of the simulated system. Surprisingly, it turns out that this simulation can be performed in polynomial time with respect to the size of the description of the simulated system only if the regular expressions used in such a system are of a very restricted form.
Keywords: Spiking neural P systems, NP-complete problems, 3-SAT.