Back to Search
Start Over
On Distributed Solution to SAT by Membrane Computing
- Source :
- International Journal of Computers Communications & Control. 13:303-320
- Publication Year :
- 2018
- Publisher :
- Agora University of Oradea, 2018.
-
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.
- Subjects :
- Class (set theory)
010308 nuclear & particles physics
Computer Networks and Communications
True quantified Boolean formula
02 engineering and technology
01 natural sciences
Square (algebra)
Computer Science Applications
Combinatorics
Computational Theory and Mathematics
0103 physical sciences
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Membrane computing
Mathematics
Sat problem
Subjects
Details
- ISSN :
- 18419836
- Volume :
- 13
- Database :
- OpenAIRE
- Journal :
- International Journal of Computers Communications & Control
- Accession number :
- edsair.doi...........f3c66792b6c48dff7ddd1873a7765f1b