Solving All-SAT Problems by P Systems

The satisfiability problem (SAT) is a well known NP-complete problem. Obtaining All of the truth assignments of SAT is called All-SAT and it has numerous applications in artificial intelligence and computer theories. Many algorithms about SAT have been built, but how to solve All-SAT is still difficult. P system is a new distributed and parallel computation model. We use membrane division, which is frequently investigated to obtain an exponential working space in a linear time, to design a family of P systems to solve All-SAT in polynomial time. Our work provides a new and effective solution to All-SAT in a distributed and parallel manner.