Inspired by the growth of dendritic trees in biological neurons, we introduce spiking neural P systems with budding rules. By applying these rules in a maximally parallel way, a spiking neural P system can exponentially increase the size of its synapse graph in a polynomial number of computation steps. Such a possibility can be exploited to efficiently solve computationally difficult problems in deterministic polynomial time, as it is shown in this paper for the NP-complete decision problem SAT
Ishdorj, T., Leporati, A., Pan, L., Wang, J. (2010). Solving NP-complete Problems by Spiking Neural P Systems with Budding Rules. In Membrane Computing: 10th International Workshop, WMC 2009 (pp.335-353). Berlin : Springer [10.1007/978-3-642-11467-0_24].
Solving NP-complete Problems by Spiking Neural P Systems with Budding Rules
LEPORATI, ALBERTO OTTAVIO;
2010
Abstract
Inspired by the growth of dendritic trees in biological neurons, we introduce spiking neural P systems with budding rules. By applying these rules in a maximally parallel way, a spiking neural P system can exponentially increase the size of its synapse graph in a polynomial number of computation steps. Such a possibility can be exploited to efficiently solve computationally difficult problems in deterministic polynomial time, as it is shown in this paper for the NP-complete decision problem SAT
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
