Antimatter as a Frontier of Tractability in Membrane Computing

• Autorzy: Díaz-Pernil D. , Peña-Cantillana F. , Alhazov A. , Freund R. , Gutiérrez-Naranjo M. A.

Identyfikatory

DOI

10.3233/FI-2014-1092

• Języki publikacji: EN

Abstrakty

EN

It is well known that the polynomial complexity class of recognizer P systems with active membranes without polarizations, without dissolution and with division for elementary and nonelementary membranes is exactly the complexity class P (see [9], Theorem 2). In this paper, we prove that if such a P systems model is endowed with antimatter and annihilation rules, then NP problems can be solved, even without non-elementary membrane division. In this way, antimatter is shown to be a frontier of tractability in Membrane Computing.

Słowa kluczowe

EN

antimatter; dissolution; annihilation operator; problem solving; annihilation reactions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 1/2
• Strony: 83--96
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Díaz-Pernil D.

• Research Group on Computational Topology and Applied Mathematics, Department of Applied Mathematics - University of Sevilla, 41012, Spain

autor

Peña-Cantillana F.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

autor

Alhazov A.

• Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Academiei 5, Chişinău, MD-2028, Republic of Moldova

autor

Freund R.

• Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria

autor

Gutiérrez-Naranjo M. A.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

Bibliografia

• [1] Alhazov, A., Aman, B., Freund, R., Păun, Gh.: Matter and Anti-Matter in Membrane Systems, DCFS 2014, 8614, Springer, 2014.
• [2] Alhazov, A., Pérez-Jiménez, M. J.: Uniform Solution of QSAT Using Polarizationless Active Membranes, Machines, Computations, Universality, 5th International Conference, MCU 2007, Orléans (J. O. Durand-Lose, M. Margenstern, Eds.), 4664, Springer, 2007.
• [3] Anderson, C. D.: The Positive Electron, Physical Review, 43, Mar 1933, 491–494.
• [4] Díaz-Pernil, D., Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A.: A Logarithmic Bound for Solving Subset Sum with P Systems, Workshop on Membrane Computing (G. Eleftherakis, P. Kefalas, Gh. Păun, G. Rozenberg, A. Salomaa, Eds.), 4860, Springer, Berlin Heidelberg, 2007, ISBN 978-3-540-77311-5.
• [5] Díaz-Pernil, D., Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A.: Solving Subset Sum in Linear Time by Using Tissue P Systems with Cell Division, IWINAC (1) (J. Mira, J. R. A´ lvarez, Eds.), 4527, Springer, Berlin Heidelberg, 2007, ISBN 978-3-540-73052-1.
• [6] Dirac, P. A. M.: The Quantum Theory of the Electron. I, Proceedings of the Royal Society A, 117(778), February 1928, 610–624, ISSN 0080-4630.
• [7] Dirac, P. A. M.: The Quantum Theory of the Electron. II, Proceedings of the Royal Society A, 118(779), March 1928, 351–361, ISSN 0080-4630.
• [8] en.w.wikipedia.org: Antimatter.
• [9] Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A., Romero-Campero, F. J.: On the Power of Dissolution in P Systems with Active Membranes, Workshop on Membrane Computing (R. Freund, Gh. Păun, G. Rozenberg, A. Salomaa, Eds.), 3850, Springer, Berlin Heidelberg, 2005, ISBN 3-540-30948-9.
• [10] Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Romero-Campero, F. J.: A Linear Solution of Subset Sum Problem by Using Membrane Creation, IWINAC (1) (J. Mira, J. R. Álvarez, Eds.), 3561, Springer, Berlin Heidelberg, 2005, ISBN 3-540-26298-9.
• [11] Leporati, A., Gutiérrez-Naranjo, M. A.: Solving Subset Sum by Spiking Neural P Systems with Precomputed Resources, Fundamenta Informaticae, 87(1), 2008, 61–77.
• [12] Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., Zandron, C.: Simulating Elementary Active Membranes With an Application to the P Conjecture, Preproceedings of the 15th International Conference on Membrane Computing, 2014.
• [13] 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, Natural Computing, 8(4), 2009, 681–702.
• [14] Metta, V. P., Krithivasan, K., Garg, D.: Computability of Spiking Neural P Systems with Anti-spikes, New Mathematics and Natural Computation (NMNC), 08(03), 2012, 283–295.
• [15] Pan, L., Păun, Gh.: Spiking Neural P Systems with Anti-Spikes, International Journal of Computers, Communications & Control, IV(3), September 2009, 273–282.
• [16] Pérez-Jiménez, M. J.: An Approach to Computational Complexity in Membrane Computing, Workshop on Membrane Computing (G. Mauri, Gh. Păun, M. J. Pérez-Jiménez, G. Rozenberg, A. Salomaa, Eds.), 3365, Springer, 2004, ISBN 3-540-25080-8.
• [17] Pérez-Jiménez, M. J., Riscos-Núñez, A.: Solving the Subset-Sum Problem by P Systems with Active Membranes, New Generation Computing, 23(4), 2005, 339–356.
• [18] Pérez-Jiménez, M. J., Riscos-Núñez, A., Romero-Jiménez, A., Woods, D.: Complexity - Membrane Division, Membrane Creation, in: The Oxford Handbook of Membrane Computing (Gh. Păun, G. Rozenberg, A. Salomaa, Eds.), Oxford University Press, Oxford, England, 2010, ISBN 9780199556670, 302–336.
• [19] Schuster, A.: Potential Matter. A Holiday Dream, Nature, 58, August 1898, 367.
• [20] Song, T., Jiang, Y., Shi, X., Zeng, X.: Small Universal Spiking Neural P Systems with Anti-Spikes, Journal of Computational and Theoretical Nanoscience, 10(4), 2013, 999–1006.
• [21] Song, T., Luo, L., He, J., Chen, Z., Zhang, K.: Solving Subset Sum Problems by Time-free Spiking Neural P Systems, Applied Mathematics & Information Sciences, 8(1), 2014, 327–332.
• [22] Sosík, P., Rodríguez-Patón, A.: Membrane Computing and Complexity Theory: A Characterization of PSPACE, Journal of Computer and System Sciences, 73(1), 2007, 137–152.
• [23] Tan, G., Song, T., Chen, Z., Zeng, X.: Spiking Neural P Systems with Anti-spikes and Without Annihilating Priority Working in a ’Flip-flop’ Way, International Journal of Computing Science and Mathematics, 4(2), July 2013, 152–162, ISSN 1752-5055.