On Distributed Solution to SAT by Membrane Computing
On Distributed Solution to SAT by Membrane Computing
复制标题
膜计算分布式SAT解决方案
DOI：
10.15837/ijccc.2018.3.3217
复制
发表时间：
2018-05
影响因子：
2.7
通讯作者：
Song B
中科院分区：
文献类型：
--
作者：
Adorna H N;Pan L;Song B
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.
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.
登录
查看更多内容
具有局部同步的异步尖峰神经 P 系统
影响因子：
8.1
作者：
Tao Song;Tao Song;Linqiang Pan;Linqiang Pan;Gheorghe Paun;Gheorghe Paun
通讯作者：
Gheorghe Paun
DOI：
--
发表时间：
2010
期刊：
The Geneva Papers on Risk and Insurance - Issues and Practice
影响因子：
--
作者：
H. Adorna;G. Paun;M. D. Jiménez
通讯作者：
H. Adorna;G. Paun;M. D. Jiménez
影响因子：
0.5
作者：
Bosheng Song;Tao Song;L. Pan
通讯作者：
Bosheng Song;Tao Song;L. Pan
DOI：
10.3217/jucs-010-05-0502
发表时间：
2004
期刊：
J. Univers. Comput. Sci.
影响因子：
--
作者：
A. Alhazov
通讯作者：
A. Alhazov
DOI：
10.15837/ijccc.2016.1.2160
发表时间：
2016
期刊：
Int. J. Comput. Commun. Control
影响因子：
--
作者：
G. Paun
通讯作者：
G. Paun