On Distributed Solution to SAT by Membrane Computing

Henry N. Adorna, Linqiang Pan, Bosheng Song

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.

Full Text:

PDF

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




DOI: https://doi.org/10.15837/ijccc.2018.3.3217



Copyright (c) 2018 Henry N. Adorna, Linqiang Pan, Bosheng Song

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2016: IF=1.374. .

IJCCC is indexed in Scopus from 2008 (CiteScore 2017 = 1.04; SNIP2017 = 0.616, SJR2017 =0.326):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.