An asynchronous P system with a DPLL algorithm for solving SAT

Abstract

Membrane computing, which is also known as P system, is a computational model inspired by the activity of living cells. Several efficient P systems, which work in a polynomial number of steps, have been proposed for solving computationally hard problems. However, most of the proposed algorithms use an exponential number of membranes, and reduction of the number of membranes must be considered in order to make the P system a more realistic model.

In the present paper, we propose an asynchronous P system with a Davis-Putnam-Logemann-Loveland (DPLL) algorithm, which is a set of rules for solving a satisfiability problem (SAT) efficiently, in an attempt to reduce the number of membranes. The proposed P system solves SAT with n variables and m clauses in O(mn2) parallel steps or O(mn22n) sequential steps.

We evaluate the number of membranes used in the proposed P system by comparison with the number of membranes used in known P systems. The experimental result demonstrates the validity and efficiency of the proposed P system.