Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Wydawca
Czasopismo
Rocznik
Tom
Strony
83--96
Opis fizyczny
Bibliogr. 23 poz.
Twórcy
autor
- Research Group on Computational Topology and Applied Mathematics, Department of Applied Mathematics - University of Sevilla, 41012, Spain
autor
- Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
autor
- Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Academiei 5, Chişinău, MD-2028, Republic of Moldova
autor
- Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-e395e467-3bb4-4b8b-bc21-8f21e620f4bb