Enhanced SAT Algorithm Based On Active Membrane P System

Boolean propositional satisfiability problem(SAT)is one of the NP-complete problems which has attracted the most attention in many years.It plays a key role in many important theoretical and application areas.Membrane computing is a branch of natural computation.It has been used as a parallel computing model aiming to solve the NP problems in polynomial time.The main research results present in this thesis are focused on developing an enhanced SAT algorithm based on active membrane P system.Active membrane P system is a type of membrane computing systems,which models the scheme of the biochemical reaction in the cells to allocate data in the relatively independent cell areas and then handle them respectively.Moreover data inside can be passed between these areas,and these areas can also vanish or be generated.Splitting rule is a kind of rule which is used on the simplification of SAT problem,by using it,a clause set can be divided into two subsets with overlapping part and be dealt with respectively,this character is clearly fit with the computational model of active membrane P system,which is the theoretical foundation of the enhanced algorithm proposed in this thesis.Based on the above motivation and ideas,the main research works of this thesis are summarized as follows:1.Analyze the computing idea of the traditional SAT algorithm based on active membrane P system,and choose a classical simplification rule of SAT problem,splitting rule,whose computing idea is complementary to the traditional algorithm's based on the analysis results to improve the traditional algorithm.2.Combine the framework of the traditional algorithm with splitting rule,and in order that splitting rule can be repeated in the whole calculation process,the other three simplification rules of SAT problem,tautology rule,one-literal rule,pure-literal rule,have been added into the algorithm's framework,resulting in an improved SAT algorithm based on active membrane P system.In the newly added simplification rules,one-literal rule and pure-literal rule can decrease the number of membrane divisions during the calculation process and can reduce the contents of membranes,in other words,they can reduce the algorithm's space and time complexity at the same time.3.Compare the computation complexity of the improved algorithm with it of the traditional algorithm to prove the advantage of the improved algorithm in terms of computing power,meanwhile demonstrate the calculation process of the improved algorithm by an instance,and compare the membrane structure of the improved algorithm and it of the traditional algorithm under the same solving progress on some nodes during the demonstration,so that the performance improvement of the improved algorithm can be visually demonstrated.