Abstract
Boolean propositional satisfiability (SAT) problem is one of the most widely studied NP-complete problems and plays an outstanding role in many domains. Membrane computing is a branch of natural computing which has been proven to solve NP problems in polynomial time with a parallel compute mode. This paper proposes a new algorithm for SAT problem which combines the traditional membrane computing algorithm of SAT problem with a classic simplification rule, the splitting rule, which can divide a clause set into two axisymmetric subsets, deal with them respectively and simultaneously, and obtain the solution of the original clause set with the symmetry of their solutions. The new algorithm is shown to be able to reduce the space complexity by distributing clauses with the splitting rule repeatedly, and also reduce both time and space complexity by executing one-literal rule and pure-literal rule as many times as possible.
| Original language | English |
|---|---|
| Article number | 1412 |
| Pages (from-to) | 1-21 |
| Number of pages | 21 |
| Journal | Symmetry |
| Volume | 11 |
| Issue number | 11 |
| DOIs | |
| Publication status | Published (in print/issue) - 15 Nov 2019 |
Bibliographical note
Funding Information:This work was supported by the National Natural Science Foundation of China(Grant No.61673320), and by the Fundamental Research Funds for the Central Universities (Grant No.2682018ZT10, No.2682018CX59).
Publisher Copyright:
© 2019 by the authors.
Keywords
- Membrane computing
- P system
- SAT problem
- Splitting rule