Research On P System For Solving Two Kinds Of Typical NP Problems

Membrane computing is a new branch of natural computing.It is a parallel computing model,which is based on the study of the function and structure of living cells,as well as the advanced structure of other tissues and organs or other cell populations.P systems is a computational system based on membrane computing model.One of the biggest advantages of P systems comparing with the traditional computing system is that it has great parallelism and serious computational power.It has been proved that the membrane computing model has the equivalent ability to calculate as the Turing machine,and could solve the NP problem in polynomial even linear time.Logic propositional satisfiability problem and knapsack problem are two types of classical NP problem and they are only solved by finding out the indivisual solution or approximate solution in electronic computer.Howerver,it is very hard to be solved when the problem size is very large.In the field of membrane computing,some shcolars have proposed the P systems to solve Satisfiability problem(referred to as SAT problem),but it still could be improved from time complexity and space complexity.There are also some scholars that have proposed to solve the knapsack problem based on the P systems,but they did not get the optimal solution.Based on this,we designed two families of P systems for solving all solutions of the satisfiability problem(referred to as All-SAT problem)and 0-1 knapsack problem in this paper.The main research work of this paper is summarized as follows:(1)Based on the study of membrane computing,we propose a family of P systems ?All-SATP for solving All-SAT problem in polynomial time.The algoritm is described in detail and the complexity analysis is given in the last.(2)Based on the P systems ?All-SATP,we propose a family of P systems ?All-SATL for solving All-SAT problem in linear time by improving the membrane structures and rule set.In the P systems ?All-SATL,the number of nested layers in the membrane is reduced to a constant level(3 layers)and the time complexity reduced to linear level.In the last,an example is given to illustrate the implementation process of the P system and verify the correctness the feasibility of the P systems ?All-SATL by the simulation program.(3)Based on the study of membrane computing,we propose a family of P systems ?KP for solving 0-1 knapsack problem.The algoritm and rules are described in detail.The average time complexity of the P systems ?KP is linear and the number of nested layers in the membrane is constant(3 layers).In the last,an example is given to illustrate the implementation process of the P system and verify the correctness the feasibility of the P systems ?KP by the simulation program.This paper researches on the All-SAT problem and the 0-1 knapsack problem by P systems.It not only enriches the theoretical research of membrane computing,but also broadens the application of membrane computing theory in NP problem.Besides,it provides a reference for solving other NP hard problems,and also provides new thought to solve other problems in the future.