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

DOI Web Site 1 References Open Access

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.

Journal

References(1)*help

See more

Related Projects

See more

Keywords

Details

Report a problem

Back to top