Research On Improved Tissue P Systems For Solving Satisfiability Problems

As the first proven NP-complete problem, the Satisfiability problem (SAT problem) of Boolean expression is the foundation stone of computer complexity theory, which is widely used in hardware circuit feasibility test, computer science(Automated theorem proving, machine vision, database and so on) and some other fields. Although the majority of the SAT problems can be solved through translating into Conjunctive Normal Form (CNF), Disjunctive Normal Form (DNF), as another form of Boolean expression, has rarely methods about solving DNF satisfiability problem. Therefore, the paper extends the SAT problem into two parts to solve. One part is for solving traditional CNF based SAT problem, and the other part is based on the solution of the DNF SAT problem. In this way, the paper can comprehensive covers all cases of SAT problem, which can broaden the application scope of Boolean expression in reality.The paper taking advantage of the membrane’s maximum parallelism, combining with the basic tissue P systems, imitating the life activity of charged organism organization in the nature, has proposed a recognized evolvable tissue P systems based on cell division to solve the SAT problem. The calculated cells growing at an exponential rate through cell division in a short period in this system, which can making each calculated cell deals with a true value distribution. The Boolean expression is processed in parallel way by rules of communication, division, evolution and output in polynomial time, which not only conforms to the biochemistry theory and practice, but also so as to be able to output "YES" or "NO" into the environment, indicating whether the Boolean expression can meet demand or not. By using the method of transforming space to time can greatly improve the calculation efficiency.Finally, the system proposed in the paper has been simulated and tested in the software and hardware. In the aspect of software, the programming language, pLingua, which is developed by natural science research group of Serbia University, is used to writing the algorithm. The simulation of the algorithm is achieved by combination of a specialized P system simulation tool, pLinguaPlugin. In the aspect of hardware, we develops a system on chip whose core is FPGA, implements the Membrane system, which is set up through the description of the hardware in VHDL language. Moreover, the simulation results have been indicated that the algorithm in this paper is correct and feasible.For a long time, many researchers are devoted to the SAT solving problem, however, the solution of SAT problem using membrane computing is not common, and the membrane computing has always been faced with the problem of hardware and software difficult to achieve. In this paper, the processing method of subdivision is utilized to deal with the SAT problem, which can broaden its application scope in reality. Taking advantage of great power and efficiency of membrane computing, the drawback of low computational efficiency due to the serial computation of previous algorithms has been settled. Finally, the proposed algorithm in this paper has been simulated by software and hardware, respectively, which overcomes the traditional biochemical reactions and promotes the pace of the membrane computing hardware implementation. Therefore, the study of solving SAT problem through membrane computing method has important realistic meaning and practical value.