On the Computational Power of Spiking Neural P Systems

Abstract

In this paper we study some computational properties of spiking neural P systems. In particular, we show that by using nondeterminism in a slightly extended version of spiking neural P systems it is possible to solve in constant time both the numerical NP-complete problem Subset Sum and the strongly NP-complete problem 3-SAT. 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 the 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 type.