On the Computational Complexity of Spiking Neural Membrane Systems with Colored Spikes

Spiking Neural P Systems are parallel and distributed computational models inspired by biological neurons, emerging from membrane computing and applied to solving computationally difficult problems. This paper focuses on the computational complexity of such systems using neuron division rules and colored spikes for the SAT problem. We prove a conjecture stated in a recent paper, showing that enhancing the model with an input module reduces computing time. Additionally, we prove that the inclusion of budding rules extends the model’s capability to solve all problems in the complexity class PSPACE. These findings advance research on Spiking Neural P Systems and their application to complex problems; however, whether both budding rules and division rules are required to extend these methods to problem domains beyond the NP class remains an open question.