On Distributed Solution to SAT by Membrane Computing
Abstract
Tissue P systems with evolutional communication rules and cell division (TPec, for short) are a class of bio-inspired parallel computational models, which can solve NP-complete problems in a feasible time. In this work, a variant of TPec, called $k$-distributed tissue P systems with evolutional communication and cell division ($k\text{-}\Delta_{TP_{ec}}$, for short) is proposed. A uniform solution to the SAT problem by $k\text{-}\Delta_{TP_{ec}}$ under balanced fixed-partition is presented. The solution provides not only the precise satisfying truth assignments for all Boolean formulas, but also a precise amount of possible such satisfying truth assignments. It is shown that the communication resource for one-way and two-way uniform $k$-P protocols are increased with respect to $k$; while a single communication is shown to be possible for bi-directional uniform $k$-P protocols for any $k$. We further show that if the number of clauses is at least equal to the square of the number of variables of the given boolean formula, then $k\text{-}\Delta_{TP_{ec}}$ for solving the SAT problem are more efficient than TPec as show in \cite{bosheng2017}; if the number of clauses is equal to the number of variables, then $k\text{-}\Delta_{TP_{ec}}$ for solving the SAT problem work no much faster than TPec.References
Adorna, H., Paun, Gh. Pérez-Jiménez, M.J. (2010): On Communication Complexity in Evolution-Communication P Systems, Rom. J. Inf. Sci. Tech., 13(2), 113-130, 2010.
Alhazov, A. (2004): On Determinism of Evolution-Communication P Systems, J. Univers. Comput. Sci. 10(5), 502-508, 2004.
Bu-o, K., Adorna, H., Pan, L. Song, B.(2017): Communicaton Complexity of Distributed Tissue-Like P Systems for Solving SAT Problem, Proc. of the 18th International Conference on Membrane Computing, Bradford, UK, 373-383, 2017.
Bu-o, K. Cabarle, F., Adorna, H., Calabia, M.(2018): Solving N-Queens Problem using dP Systems with Active Membranes, Theor. Comput. Sci., 2018.
Cavaliere, M. (2003): Evolution-Communication P Systems, In: Paun, Gh. et al, (Eds.) LNCS, Springer, Heidelberg, 2597, 134-145, 2003. https://doi.org/10.1007/3-540-36490-0_10
Csuhaj-Varjú, E., Margenstern, M., Vazil, G., Verlan, S. (2007): On Small Universal Antiport P System, Theor. Comput. Sci., 372(2-3), 152-164, 2007. https://doi.org/10.1016/j.tcs.2006.11.023
Csuhaj-Varjú, E., Vaszil, G. (2012): Finite dP Automata Versus Multi-head Finite Automata. In: Gheorghe, M. et al. (Eds.): LNCS, Springer, Heidelberg, 7184, 120-138, 2012. https://doi.org/10.1007/978-3-642-28024-5_10
DÃaz-Pernil, D., Pe-a-Cantillana, F., Gutiérrez-Naranjo, M.A. (2013): A Parallel Algorithm for Skeletonizing Images by Using Spiking Neural P Systems, Neurocomputing, 115, 81-91, 2013. https://doi.org/10.1016/j.neucom.2012.12.032
Dzitac, I. (2015): Impact of Membrane Computing and P Systems in ISI WoS. Celebrating the 65th Birthday of Gheorghe Paun, Int. J. Comput. Commun, 10(5), 617-626, 2015.
Elias, S., Gokul, V, Krithivasan, K., Gheorghe, M., Zhang, G. (2012): A Variant of Distributed P Systems for Real Time Cross Layer Optimization, J. Univers. Comput. Sci., 18(13), 1760-1781, 2012.
Frisco, P., Govan, G., Leporati, A. (2012): Asynchronous P Systems with Active Membranes, Theor. Comput. Sci., 429, 74-86, 2012. https://doi.org/10.1016/j.tcs.2011.12.026
Gazdag, Z. (2014): Solving SAT by P Systems with Active Membranes in Linear Time in the Number of Variables. In: Alhazov, A. et al. (Eds.) LNCS, Springer, Heidelberg, 8340, 189-205, 2014. https://doi.org/10.1007/978-3-642-54239-8_14
Gutiérrez-Naranjo, M.A., MartÃnez-del-Amor, M.A., Pérez-Jurtado, I., Pérez-Jiménez, M.J. (2009): Solving N-Queens Puzzle with P Systems. In: Proc. of the 7th Brainstorming Week on Membrane Computing, Sevilla, Spain, 199-210, 2009.
Hernandez, N., Juayong, R., Adorna, H. (2014): On the Communication Complexity of Some Hard Problems in ECPe Systems. In: Alhazov, A. et al. (Eds.): LNCS, Springer, Heidelberg, 8340, 206-224, 2014. https://doi.org/10.1007/978-3-642-54239-8_15
MacÃas-Ramos, L.F., Valencia-Cabrera, L., Song, B., Pan, L., Pérez-Jiménez, M.J. (2015): A P-Lingua Based Simulator for P Systems with Symport/Antiport Rules, Fund. Informa., 139(2), 211-277, 2015. https://doi.org/10.3233/FI-2015-1232
MartÃnez-del-Amor, M.A., GarcÃa-Quismondo, M., MacÃas-Ramos, L.F., Valencia-Cabrera, L., Riscos-Nú-ez, A., Pérez-Jiménez, M.J. (2015): Simulating P Systems on GPU Devices: A Survey, Fund. Informa., 136(3), 269-284, 2015.
Pan, L., Paun, Gh. (2009): Spiking Neural P Systems with Anti-Spikes, Int. J. Comput. Commun., 4(3), 273-282, 2009. https://doi.org/10.15837/ijccc.2009.3.2435
Pan, L., Pérez-Jiménez, M.J. (2010): Computational Complexity of Tissue-Like P Systems, J. Complexity, 26(3), 296-315, 2010. https://doi.org/10.1016/j.jco.2010.03.001
Paun, Gh. (2000): Computing with Membranes, J. Comput. Syst. Sci., 61(1), 108-143, 2000. https://doi.org/10.1006/jcss.1999.1693
Paun, Gh. (2016): Membrane Computing and Economics: A General View, Int. J. Comput. Commun., 11(1), 105-112, 2016. https://doi.org/10.15837/ijccc.2016.1.2160
Paun, Gh., Pérez-Jiménez, M.J. (2010): Solving Problem in a DistributedWay in Membrane Computing: dP Sytems, Int. J. Comput. Commun., 5, 238-259, 2010. https://doi.org/10.15837/ijccc.2010.2.2478
Paun, Gh., Pérez-Jiménez, M.J. (2012): An Infinite Hierarchy of Languages Defined by dP Systems, Theor. Comput. Sci., 431, 4-12, 2012. https://doi.org/10.1016/j.tcs.2011.12.053
Paun, Gh. Rozenberg, G., Salomaa, A. (Eds.)(2010): The Oxford Handbook of Membrane Computing, Oxford University Press, New York, 2010.
Peng, H., Wang, J., Pérez-Jiménez, M.J., Riscos-Nú-ez, A. (2015): An Unsupervised Learning Algorithm for Membrane Computing, Inf. Sci., 304, 80-91, 2015. https://doi.org/10.1016/j.ins.2015.01.019
Song, T., Pan, L. (2016): Spiking Neural P Systems with Request Rules, Neurocomputing, 193, 193-200, 2016. https://doi.org/10.1016/j.neucom.2016.02.023
Song, T., Pan, L., Paun, Gh. (2013): Asynchronous Spiking Neural P Systems with Local Synchronization, Inf. Sci. 219, 197-207, 2013. https://doi.org/10.1016/j.ins.2012.07.023
Song, B., Pan, L. (2016): The Computational Power of Tissue-Like P Systems with Promoters, Theor. Comput. Sci., 641, 43-52, 2016. https://doi.org/10.1016/j.tcs.2016.05.022
Song, B., Song, T., Pan, L. (2017): A Time-Free Uniform Solution to Subset Sum Problem by Tissue P Systems with Cell Division, Math. Struct. Comp. Sci., 27(1), 17-32, 2017. https://doi.org/10.1017/S0960129515000018
Song, B., Zhang, C., Pan, L. (2017): Tissue-Like P Systems with Evolutional Symport/Antiport Rules, Inf. Sci., 378, 177-193, 2017. https://doi.org/10.1016/j.ins.2016.10.046
Valencia-Cabrera, L., Orellana-MartÃn, D., MartÃnez-del-Amor, M.A., Riscos-Nú-ez, A., Pérez-Jiménez, M.J. (2017): Cooperation in Transport of Chemical Substances: A Complexity Approach within Membrane Computing, Fund. Informa., 154(1-4), 373-385, 2017. https://doi.org/10.3233/FI-2017-1572
Valencia-Cabrera, L., Orellana-MartÃn, D., MartÃnez-del-Amor, M.A., Riscos-Nú-ez, A., Pérez-Jiménez, M.J. (2017): Reaching Efficiency through Collaboration in Membrane Systems: Dissolution, Polarization and Cooperation, Theor. Comput. Sci., 701, 226-234, 2017. https://doi.org/10.1016/j.tcs.2017.04.015
Valencia-Cabrera, L., Wu, T., Zhang, Z.,Pan, L., Pérez-Jiménez, M.J. (2016): A Simulation Software Tool for Cell-Like Spiking Neural P Systems, Rom. J. Inf. Sci. Tech., 20(1), 71-84, 2016.
Wu, T., Zhang, Z., Paun, Gh., Pan, L. (2016): Cell-Like Spiking Neural P Systems, Theor. Comput. Sci., 623, 180-189, 2016. https://doi.org/10.1016/j.tcs.2015.12.038
Yao, A.C. (1979): Some Complexity Questions Related to Distributed Computing, In: Proceedings of the eleventh annual ACM symposium on Theory of computing, 209-213, 1979.
Zandron, C., Leporati, A., Ferretti, C., Mauri, G., Pérez-Jiménez, M.J. (2008): On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution, Fund. Informa., 87(1), 79-91, 2008.
Zhang, G., Rong, H., Neri, F., Pérez-Jiménez, M.J. (2014): An Optimization Spiking Neural P System for Approximately Solving Combinatorial Optimization Problems, Int. J. Neural Syst., 24, 1-16, 2014. https://doi.org/10.1142/S0129065714400061
Zhang, X., Pan, L., Paun, A. (2015): On the Universality of Axon P Systems, IEEE T. Neur. Net. Lea., 26(11), 2816-2829, 2015. https://doi.org/10.1109/TNNLS.2015.2396940
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
