Solving SUBSET SUM by Spiking Neural P Systems with Pre-computed Resources

• Autorzy: Leporati A. , Gutiérrez-Naranjo M.
• Języki publikacji: EN

Abstrakty

EN

Recently the possibility of using spiking neural P systems for solving computationally hard problems has been considered. Such solutions assume that some (possibly exponentially large) pre–computed resources are given in advance, provided that their structure is “regular” and they do not contain neither “hidden information” that simplify the solution of specific instances, nor an encoding of all possible solutions (that is, an exponential amount of information that allows to cheat while solving the instances of the problem). In this paper we continue this research line, and we investigate the possibility of solving numerical NP-complete problems such as SUBSET SUM. In particular, we first propose a semi–uniform family of spiking neural P systems in which every system solves a specific instance of SUBSET SUM. Then, we exploit a technique used to calculate ITERATED ADDITION with Boolean circuits to obtain a uniform family of spiking neural P systems in which every system is able to solve any instance of SUBSET SUM of a fixed size. All the systems here considered are deterministic, and their size generally grows exponentially with respect to the instance size.

Słowa kluczowe

EN

membrane computing; spiking neural P systems; NP-complete problems; subset sum

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 1
• Strony: 61--77
• Opis fizyczny: bibliogr. 37 poz.

Twórcy

autor

Leporati A.

autor

Gutiérrez-Naranjo M.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Universita degli Studi di Milano – Bicocca, Viale Sarca 336/14, 20126 Milano, Italy,

Bibliografia

• [1] Alhazov, A., Pérez-Jiménez, M. J.: Uniform Solution to QSAT Using Polarizationless Active Membranes, Fourth BrainstormingWeek onMembrane Computing (M. A. Gutiérrez-Naranjo,Gh. Păun, A. Riscos-Núñez, F. J. Romero-Campero, Eds.), RGCN Report 02/2006, Sevilla University, Fénix Editora, Vol. I, 2006, 29-40.
• [2] Balcázar, J. L, Díaz, J., Gabarró, J.: Structural Complexity, Voll. I and II, Springer-Verlag,Berlin, 1988-1990.
• [3] Chen, H., Freund, R., Ionescu, M., Păun, Gh., Pérez-Jiménez, M. J.: On String Languages Generated by Spiking Neural P Systems, Fourth Brainstorming Week on Membrane Computing (M. A. Gutiérrez-Naranjo, Gh. Păun, A.Riscos-Núñez, F. J. Romero-Campero, Eds.), RGCN Report 02/2006, Sevilla University, Fénix Editora, Vol. I, 2006, 169-194.
• [4] Chen, H., Ionescu,M., Ishdorj, T.-O: On the Efficiency of Spiking Neural P Systems, Proc. 8th Intern. Conf. on Electronics, Information, and Communication, Ulanbator,Mongolia, June 2006, 49-52.
• [5] Cormen, T. H., Leiserson, C. H, Rivest, R. L.: Introduction to Algorithms, MIT Press, Boston, 1990.
• [6] García-Arnau, M., Pérez, D., Rodríguez-Pat´on, A., Sosík, P.: Spiking Neural P Systems. Stronger Normal Forms, Fifth BrainstormingWeek onMembrane Computing (M. A. Gutiérrez-Naranjo,Gh. Păun, A. Romero-Jiménez, A. Riscos-Núñez, Eds.), RGCN Report 01/2007, Sevilla University, Fénix Editora, 2007, 157-178.
• [7] Garey, M. R., Johnson, D. S.: Computers and Intractability. A Guide to the Theory on NP-Completeness, W.H. Freeman and Company, 1979.
• [8] Gerstner, W., Kistler, W.: Spiking Neuron Models. Single Neurons, Populations, Plasticity, Cambridge University Press, 2002.
• [9] Gutiérrez-Naranjo,M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A.: A Fast P System for Finding a Balanced 2-partition. Soft Computing, 9(9), 2005, 673-678.
• [10] Ibarra, O. H., Păun, A., Păun, Gh., Rodríguez-Pat´on,A., Sosík, P.,Woodworth, S.: Normal Forms for Spiking Neural P Systems, Theoretical Computer Science, 372(2-3), 2007, 196-217.
• [11] Ionescu, M., Păun, A., Păun, Gh., Pérez-Jiménez, M. J.: Computing with Spiking Neural P Systems: Traces and Small Universal Systems, DNA Computing, 12th International Meeting on DNA Computing (DNA12), Revised Selected Papers (C. Mao, T. Yokomori, B.-T. Zhang, Eds.), LNCS 4287, Springer-Verlag, Berlin, 2006, 1-16.
• [12] Ionescu, M., Păun, Gh., Yokomori, T.: Spiking Neural P Systems, Fundamenta Informaticae, 71(2-3), 2006, 279-308.
• [13] Ishdorj, T.-O., Leporati, A.: Uniform Solutions to SAT and 3-SAT by Spiking Neural P Systems with Precomputed Resources, Natural Computing, in press, DOI 10.1007/s11047-008-9081-0.A preliminary version appeared as Turku Centre for Computer Science - TUCS Report No. 876, 2008.
• [14] Krishna, S. N., Rama, R.: A Variant of P Systems with Active Membranes: Solving NP-complete Problems, Romanian Journal of Information Science and Technology, 2(4), 1999, 357-367.
• [15] Leporati, A.,Mauri, G., Zandron, C., Păun, Gh., Pérez-Jiménez,M. J.: Uniform Solutions to SAT and SUBSET SUM by Spiking Neural P Systems, submitted.
• [16] Leporati, A., Zandron, C., Ferretti, C.,Mauri, G.: On the Computational Power of Spiking Neural P Systems, Intern. J. Unconventional Computing, 2007, in press.
• [17] Leporati, A. Zandron,, C., Ferretti, C., Mauri, G.: Solving Numerical NP-complete Problems with Spiking Neural P Systems, Membrane Computing, International Workshop, WMC8, Selected and Invited Papers, (G.Eleftherakis, P. Kefalas, Gh. Păun, G. Rozenberg, A. Salomaa, Eds.), LNCS 4860, Springer-Verlag, Berlin, 2007. 336-352.
• [18] 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), 2006, 127-146.
• [19] Maass,W.: Computing with spikes, Special Issue on Foundations of Information Processing of TELEMATIK, 8(1), 2002, 32-36.
• [20] Maass, W., Bishop, C. (Eds.), Pulsed Neural Networks, MIT Press, Cambridge (MA), 1999.
• [21] Martín Vide, C., Pazos, J., Păun, Gh., Rodríguez Pat´on, A.: A New Class of Symbolic Abstract Neural Nets: Tissue P Systems, Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, LNCS 2387, Springer-Verlag, Berlin, 2002, 290-299.
• [22] Martín Vide, C., Pazos, J., Păun, Gh., Rodríguez Pat´on, A.: Tissue P Systems, Theoretical Computer Science, 296, 2003, 295-326.
• [23] Obtulowicz, A: Deterministic P Systems for Solving SAT Problem, Romanian Journal of Information Science and Technology, 4(1-2), 2001, 551-558.
• [24] Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994.
• [25] Păun, A., Păun, Gh.: Small Universal Spiking Neural P Systems, BioSystems, 90(1), 2007, 48-60.
• [26] Păun, Gh.: Computing with Membranes, Journal of Computer and System Sciences, 1(61), 2000, 108-143. See also Turku Centre for Computer Science - TUCS Report No. 208, 1998.
• [27] Păun, Gh.: Computing with Membranes. An Introduction, Bulletin of the EATCS, 67, 1999, 139-152.
• [28] Păun, Gh.: P Systems with Active Membranes: Attacking NP-complete Problems, Journal of Automata, Languages and Combinatorics, 6(1), 2001, 75-90.
• [29] Păun, Gh.: Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002.
• [30] Păun, Gh., Pérez-Jiménez, M. J., Rozenberg, G.: Infinite spike trains in spiking neural P systems, submitted.
• [31] Păun, Gh., Rozenberg, G.: A Guide to Membrane Computing, Theoretical Computer Science, 287(1), 2002, 73-100.
• [32] Păun, Gh., Sakakibara, Y., Yokomori, T.: P Systems on Graphs of Restricted Forms, Publicationes Mathematicae Debrecen, 60, 2002, 635-660.
• [33] Pérez-Jiménez, M. J., Riscos-Núñez, A.: A Linear-time Solution to the KNAPSACK Problem Using P Systems with ActiveMembranes,Membrane Computing, InternationalWorkshop,WMC 2003, Revised Selected and Invited Papers (C. Martín-Vide, Gh. Păun, G. Rozenberg, A. Salomaa, Eds.), LNCS 2933, Springer-Verlag, Berlin, 2004, 250-268.
• [34] Pérez-Jiménez, M. J., Riscos-Núñez, A.: Solving the SUBSET SUM Problem by Active Membranes, New Generation Computing, 23(4), 2005, 367-384.
• [35] Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach, Springer-Verlag, Berlin, 1999.
• [36] Zandron, C., Ferretti, C., Mauri, G.: Solving NP-complete Problems Using P Systems with Active Membranes, Unconventional Models of Computation (I. Antoniou, C.S. Calude, M.J. Dinneen, Eds.), Springer-Verlag, Berlin, 2000, 289-301.
• [37] The P systems Web page: http://ppage.psystems.eu