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

Le Hao, Jun Liu

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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 languageEnglish
Article number1412
Pages (from-to)1-21
Number of pages21
JournalSymmetry
Volume11
Issue number11
DOIs
Publication statusPublished - 15 Nov 2019

Keywords

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

Fingerprint

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