POLYNOMIAL TIME-BOUNDED COMPUTATIONS IN SPIKING NEURALP SYSTEMS

摘要

The paper introduces a formal framework for the study of computational power of spiking neural (SN) P systems. We define complexity classes of uniform families of recognizer SN P systems with and without input, in a way which is standard in P systems theory. Then we study properties of the resulting complexity classes, extending previous results on SN P systems. We demonstrate that the computational power of several variants of confluent SN P systems, under polynomial time restriction, is characterized by classes ranging from P to PSPACE.