More Web Proxy on the site http://driver.im/

Article

Solving numerical NP-complete problems with spiking neural P systems

Authors:

Alberto Leporati,

Claudio Zandron,

Claudio Ferretti,

Giancarlo MauriAuthors Info & Claims

WMC'07: Proceedings of the 8th international conference on Membrane computing

Pages 336 - 352

Published: 25 June 2007 Publication History

Abstract

Starting from an extended nondeterministic spiking neural P system that solves the Subset SUM problem in a constant number of computation steps, recently proposed in a previous paper, we investigate how different properties of spiking neural P systems affect the capability to solve numerical NP-complete problems. In particular, we show that by using maximal parallelism we can convert any given integer number from the usual binary notation to the unary form, and thus we can initialize the above P system with the required (exponential) number of spikes in polynomial time. On the other hand, we prove that this conversion cannot be performed in polynomial time if the use of maximal parallelism is forbidden. Finally, we show that if we can choose whether each neuron works in the nondeterministic vs. deterministic and/or in the maximal parallel vs. sequential way, then there exists a uniform family of spiking neural P systems that solves the SUBSET SUM problem.

References

[1]

Chen, H., Freund, R., Ionescu, M., Paun, G., Pérez-Jiménez, M.J.: On String Languages Generated by Spiking Neural P Systems. In: Gutiérrez-Naranjo, M.A., Paun, G., Riscos-Núñez, A., Romero-Campero, F.J. (eds.) Fourth Brainstorming Week on Membrane Computing, vol. I, RGCN Report 02/2006, Research Group on Natural Computing, Sevilla University, pp. 169-194. Fénix Editora (2006)

[2]

Cormen, T.H., Leiserson, C.H., Rivest, R.L.: Introduction to Algorithms. MIT Press, Boston (1990)

[3]

García-Arnau, M., Peréz, D., Rodríguez-Patón, A., Sosík, P.: Spiking Neural P Systems: Stronger Normal Forms. In: Gutiérrez-Naranjo, M.A., Paun, G., Romero-Jiménez, A., Riscos-Núñez, A. (eds.) Fifth Brainstorming Week on Membrane Computing, RGCN Report 01/2007, Research Group on Natural Computing, Sevilla University, pp. 157-178. Fénix Editora (2007)

[4]

Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory on NP-Completeness. W.H. Freeman and Company, New York (1979)

[5]

Ibarra, O.H., Paun, A., Paun, G., Rodríguez-Patón, A., Sosík, P., Woodworth, S.: Normal Forms for Spiking Neural P Systems. Theoretical Computer Science 372(2- 3), 196-217 (2007)

[6]

Ionescu, M., Paun, G., Yokomori, T.: Spiking Neural P Systems. Fundamenta Informaticae 71(2-3), 279-308 (2006)

[7]

Ionescu, M., Paun, A., Paun, G., Pérez-Jiménez, M.J.: Computing with Spiking Neural P Systems: Traces and Small Universal Systems. In: Mao, C., Yokomori, T. (eds.) DNA Computing. LNCS, vol. 4287, pp. 1-16. Springer, Heidelberg (2006)

[8]

Leporati, A., Zandron, C., Ferretti, C., Mauri, G.: On the Computational Power of Spiking Neural P Systems. In: Gutiérrez-Naranjo, M.A., et al. (eds.) Fifth Brainstorming Week on Membrane Computing, Research Group on Natural Computing, Sevilla University, pp. 227-245. Fénix Editora (2007)

[9]

Leporati, A., Zandron, C., Gutiérrez-Naranjo, M.A.: P Systems with Input in Binary Form. International Journal of Foundations of Computer Science 17(1), 127- 146 (2006)

[10]

Martín-Vide, C., Pazos, J., Paun, G., Rodríguez-Patón, A.: A New Class of Symbolic Abstract Neural Nets: Tissue P Systems. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 290-299. Springer, Heidelberg (2002)

[11]

Paun, G.: Computing with Membranes. Journal of Computer and System Sciences 61, 108-143 (2000), see also Turku Centre for Computer Science -- TUCS Report No. 208 (1998), available at: http://www.tucs.fi/Publications/techreports/TR208.php

[12]

Paun, G.: Membrane Computing. An Introduction. Springer, Berlin (2002)

[13]

Paun, G., Pérez-Jiménez, M.J., Rozenberg, G.: Infinite Spike Trains in Spiking Neural P Systems (submitted for publication)

[14]

Zandron, C., Ferretti, C., Mauri, G.: Solving NP-Complete Problems Using P Systems with Active Membranes. In: Antoniou, I., Calude, C.S., Dinneen, M.J. (eds.) Unconventional Models of Computation, pp. 289-301. Springer, London (2000)

[15]

The P systems Web page: http://psystems.disco.unimib.it/

Cited By

Cabarle FAdorna HPérez-Jiménez M(2016)Sequential spiking neural P systems with structural plasticity based on max/min spike numberNeural Computing and Applications10.1007/s00521-015-1937-527:5(1337-1347)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00521-015-1937-5
Cabarle FAdorna HPérez-Jiménez MSong T(2015)Spiking neural P systems with structural plasticityNeural Computing and Applications10.1007/s00521-015-1857-426:8(1905-1917)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s00521-015-1857-4
Xue JLiu X(2012)Solving directed hamilton path problem in parallel by improved SN p systemProceedings of the 2012 international conference on Pervasive Computing and the Networked World10.1007/978-3-642-37015-1_60(689-696)Online publication date: 28-Nov-2012
https://dl.acm.org/doi/10.1007/978-3-642-37015-1_60
Show More Cited By

Solving numerical NP-complete problems with spiking neural P systems

Recommendations

Splitting NP-Complete Sets

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long-standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glaßer et al., complete sets for all of the following ...
Spiking neural p systems with astrocytes

In a biological nervous system, astrocytes play an important role in the functioning and interaction of neurons, and astrocytes have excitatory and inhibitory influence on synapses. In this work, with this biological inspiration, a class of computation ...
Spiking neural P systems with cooperative synapses
Highlights
- The spiking neural P systems with cooperative synapses (SNPCS systems) is proposed.
Abstract
Spiking neural P systems (SN P systems) are a class of neuron-inspired computation models, where each synapse independently passes a spike produced by the pre-synaptic neuron to the post-synaptic neuron. Motivated by the mechanism of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

WMC'07: Proceedings of the 8th international conference on Membrane computing

June 2007

453 pages

ISBN:3540773118

Editors:
George Eleftherakis
CITY College, Affiliated Institution of the University of Sheffield, Computer Science Department, Thessaloniki, Greece
,
Petros Kefalas
CITY College, Affiliated Institution of the University of Sheffield, Computer Science Department, Thessaloniki, Greece
,
Gheorghe Pǎun
Institute of Mathematics of the Romanian Academy, Bucharest, Romania
,
Grzegorz Rozenberg
Leiden University, Leiden Institute of Advanced Computer Science, Leiden, The Netherlands
,
Arto Salomaa
Turku Centre for Computer Science, Turku, Finland

Sponsors

SEERC: South-East European Research Centre
City College

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 25 June 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
3
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cabarle FAdorna HPérez-Jiménez M(2016)Sequential spiking neural P systems with structural plasticity based on max/min spike numberNeural Computing and Applications10.1007/s00521-015-1937-527:5(1337-1347)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00521-015-1937-5
Cabarle FAdorna HPérez-Jiménez MSong T(2015)Spiking neural P systems with structural plasticityNeural Computing and Applications10.1007/s00521-015-1857-426:8(1905-1917)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s00521-015-1857-4
Xue JLiu X(2012)Solving directed hamilton path problem in parallel by improved SN p systemProceedings of the 2012 international conference on Pervasive Computing and the Networked World10.1007/978-3-642-37015-1_60(689-696)Online publication date: 28-Nov-2012
https://dl.acm.org/doi/10.1007/978-3-642-37015-1_60
Ceterchi RTomescu A(2011)Computing the maximum bisimulation with spiking neural P systemsComputation, cooperation, and life10.5555/2017728.2017744(151-157)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2017728.2017744
Ishdorj TLeporati APan LWang J(2009)Solving NP-Complete problems by spiking neural p systems with budding rulesProceedings of the 10th international conference on Membrane Computing10.1007/978-3-642-11467-0_24(335-353)Online publication date: 24-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-11467-0_24

View Options

View options

Media

Figures

Other

Tables

View Table of Contents