Enhanced Membrane Computing Algorithm for SAT Problems Based on the Splitting Rule

Le Hao, Jun Liu

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
42 Downloads (Pure)


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 languageEnglish
Article number1412
Pages (from-to)1-21
Number of pages21
Issue number11
Publication statusPublished (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.


  • Membrane computing
  • P system
  • SAT problem
  • Splitting rule


Dive into the research topics of 'Enhanced Membrane Computing Algorithm for SAT Problems Based on the Splitting Rule'. Together they form a unique fingerprint.

Cite this