Published in

Agora University of Oradea, International Journal of Computers Communications and Control, 3(13), p. 303-320, 2018

DOI: 10.15837/ijccc.2018.3.3217

Links

Tools

Export citation

Search in Google Scholar

On Distributed Solution to SAT by Membrane Computing

Journal article published in 2018 by Henry N. Adorna, Linqiang Pan ORCID, Bosheng Song
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown
Data provided by SHERPA/RoMEO

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{-}Δ_{TP_{ec}}$, for short) is proposed. A uniform solution to the SAT problem by $k\text{-}Δ_{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{-}Δ_{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{-}Δ_{TP_{ec}}$ for solving the SAT problem work no much faster than TPec.