Solving3-SAT And SAT Problem With Membrane Creation

As a new branch of natural computing, membrane computing creates a distributedparallel computing model, while it was abstracted form the characteristics of cells,including the structure and functioning, so that the model has good computationalperformance. From the time membrane computing proposed, researchers havedemonstrated that the computing models of membrane computing not only has thecomputing power equal to Turing machine, but can effectively solve many difficultproblems of computing, NP-complete problems for example. Membrane computing waslisted as the forefront of the rapid development of the field of computational science byISI at2003.In this paper, by using P systems with membrane creation, we give a solution for3-SATproblem in polynomial time, on which we get a time-free solution for3-SAT problem, andat last we get a time-free solution for the SAT problem. The solutions for3-SAT and theSAT problem given in this paper can create an exponential number of membranes in acertain period of time, and each membrane takes for an assignment of one Booleanvariable, then check whether the problem can be satisfied or not in the membrane, and getthe answer that whether the problem can be satisfied or not in any membrane.This is the first time-free solution for the SAT problem. In actual biological cells, therules are difficult to be executed synchronously, so the research to find time-free solutionsmakes sense. The solutions given in this paper are complete solutions which canaccurately determine whether the problem can be satisfied or not. In addition, the maximalparallelism of membrane computing ensures the solution efficiency of the solutions.