An asynchronous P system with branch and bound for solving the satisfiability problem

Abstract

Membrane computing, which is a computational model based on cell activity, has considerable attention as one of new paradigms of computations. In the general membrane computing, computationally hard problems have been solved in a polynomial number of steps using an exponential number of membranes. However, reduction of the number of membranes must be considered to make P system more realistic model.

In the paper, we propose an asynchronous P system with branch and bound, which is a well known optimization technique, to reduce the number of membranes. The proposed P system solves the satisfiability problem (SAT) with n variables and m clauses, and works in O(m2^n)$ sequential steps or O(mn) parallel steps.

In addition, the number of membranes used in the proposed P system is evaluated using a computational simulation. The experimental result shows validity and efficiency of the proposed P system.