Presentation
On the Efficiency of Spiking Neural P Systems
Author/s | Chen, Haiming
Ionescu, Mihai Ishdorj, Tseren-Onolt |
Publication Date | 2006 |
Deposit Date | 2016-03-09 |
Published in |
|
ISBN/ISSN | 8461106814 |
Abstract | Spiking neural P systems were recently introduced in 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 ... Spiking neural P systems were recently introduced in 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
mihaitserenf.pdf | 164.8Kb | [PDF] | View/ | |