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

Area of Science:

• Computational intelligence
• Theoretical computer science
• Membrane computing

Background:

• Spiking Neural P Systems are bio-inspired parallel computing models.
• They are used for computationally difficult problems.
• This study investigates their computational complexity.

Purpose of the Study:

• To analyze the computational complexity of Spiking Neural P Systems.
• To investigate the impact of neuron division rules and colored spikes.
• To address the SAT problem within this framework.

Main Methods:

• Utilizing neuron division rules and colored spikes.
• Enhancing the model with an input module.
• Incorporating budding rules into the system.

Main Results:

• Proved a conjecture on reduced computing time with an input module.
• Demonstrated that budding rules extend capabilities to the PSPACE complexity class.
• Identified an open question regarding the necessity of both rule types for problems beyond NP.

Conclusions:

• Enhancements to Spiking Neural P Systems significantly impact computational efficiency and problem-solving scope.
• The model's capacity is extended to PSPACE, showing its potential for complex computational tasks.
• Further research is needed to fully understand the role of budding and division rules for problems exceeding NP-class complexity.