Agora University of Oradea, International Journal of Computers Communications and Control, 3(13), p. 303-320, 2018
DOI: 10.15837/ijccc.2018.3.3217
Full text: Download
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.