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

DOI Web Site 被引用文献2件 参考文献1件 オープンアクセス

抄録

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.

収録刊行物

被引用文献 (2)*注記

もっと見る

参考文献 (1)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ