On the Efficiency of Spiking Neural P Systems (bibtex)
by Chen, Haiming, Ionescu, Mihai and Ishdorj, Tseren-Onolt
Abstract:
Spiking neural P systems were recently introduced in citespiking and proved to be Turing complete as number computing devices. In this paper we show that these systems are also computationally efficient. Specifically, we present a variant of spiking neural P systems which have, in their initial configuration, an arbitrarily large number of inactive neurons which can be activated (in an exponential number) in polynomial time. Using this model of P systems we can deterministically solve the satisfiability problem (SAT) in constant time.
Reference:
On the Efficiency of Spiking Neural P Systems (Chen, Haiming, Ionescu, Mihai and Ishdorj, Tseren-Onolt), In Proc. 8th International Conference on Electronics, Information, and Communication (ICEIC2006), Ulaanbaatar, June 2006, 2006.
Bibtex Entry:
@InProceedings{inp64,
author    = {Chen, Haiming AND Ionescu, Mihai AND Ishdorj, Tseren-Onolt},
title     = {On the Efficiency of Spiking Neural P Systems},
booktitle = {Proc. 8th International Conference on Electronics, Information, and Communication (ICEIC2006), Ulaanbaatar, June 2006},
year      = {2006},
pages     = {49-52},
abstract  = {Spiking neural P systems were recently introduced in cite{spiking} and proved to be Turing complete as number computing devices. In this paper we show that these systems are also computationally efficient. Specifically, we present a variant of spiking neural P systems which have, in their initial configuration, an arbitrarily large number of inactive neurons which can be activated (in an exponential number) in polynomial time. Using this model of P systems we can deterministically solve the satisfiability problem (SAT) in constant time.},
file      = {HMT2006a.pdf:pdfs/HMT2006a.pdf:PDF},
}