Computational Complexity of Spiking Neural P Systems

From the very beginning, the ability to solve computationally hard problems has been one of the main characteristics of membrane systems that has been measured. Computational complexity classes in this framework have been described in a formal way for several classes of P systems, but authors do not have a common criteria about the definition of solutions of decision problems in spiking neural P systems, due to their special characteristics (such as the input pattern or the singleton alphabet). In this chapter, a review of computational complexity theory is taken, focusing on some specific definitions that are useful for the rest of the chapter. After that, formal definitions of complexity classes in membrane computing, in particular of spiking neural P systems are explored. Using different variants, efficient solutions to NP-complete problems are explained, and some frontiers of efficiency are provided.