Research of Improved Tissue-like P System for Solving Satisfiability Problem

Satisfiability problem is the first NP-complete problem that is not only the basic problem of logic but also the main content of computer science and artificial intelligence research nowadays. In this paper, the maximum parallelism of P system and the basic tissue-like P system are utilized to imitate life activities of charged organisms in nature; a recognizable evolutionary tissue-like P system based on cell division is proposed to solve the satisfiability problem. The system can obtain exponentially growing computing cells by cell division in a short time and each cell processes one truth value assignment situation; carries out parallel processing of the Boolean expression in polynomial time by using communication rules, splitting rule, evolutionary rule and output rules. To prove the correctness and efficiency of the algorithm, this paper completes the simulation of the algorithm by using pLingua Plugin that is dedicated to P system simulation, which proves that the algorithm is correct and feasible, and improves the calculation efficiency by changing the space for time.

Satisfiability problem, Membrane computing, Tissue-like P system

Huang Yourui, Ge Pingping, Xu Jiachang, Tang Chaoli, Research of Improved Tissue-like P System for Solving Satisfiability Problem. 2019 International Computer Science and Applications Conference (ICSAC 2019). 2019: 67-71.