We investigate some computational properties of spiking neural P systems. In particular, we first show that nondeterministic spiking neural P systems are able to solve (in a semi-uniform setting) the NP-complete problem 3-SAT in constant time. Then, we show how to simulate a universal deterministic spiking neural P system with a deterministic Turing machine, in a time which is polynomial with respect to the execution time of the simulated system. Surprisingly, it turns out that this simulation can be performed in polynomial time with respect to the size of the description of the simulated system only if the regular expressions used in such a system are of a very restricted form.
Leporati, A., Zandron, C., Ferretti, C., Mauri, G. (2009). On the computational power of spiking neural P systems. INTERNATIONAL JOURNAL OF UNCONVENTIONAL COMPUTING, 5(5), 459-473.
On the computational power of spiking neural P systems
LEPORATI, ALBERTO OTTAVIO;ZANDRON, CLAUDIO;FERRETTI, CLAUDIO;MAURI, GIANCARLO
2009
Abstract
We investigate some computational properties of spiking neural P systems. In particular, we first show that nondeterministic spiking neural P systems are able to solve (in a semi-uniform setting) the NP-complete problem 3-SAT in constant time. Then, we show how to simulate a universal deterministic spiking neural P system with a deterministic Turing machine, in a time which is polynomial with respect to the execution time of the simulated system. Surprisingly, it turns out that this simulation can be performed in polynomial time with respect to the size of the description of the simulated system only if the regular expressions used in such a system are of a very restricted form.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
