From SAT to SAT-UNSAT using P systems with dissolution rules

Abstract

DP is the class of problems that are the differences between two languages from NP. Most difficult problems from DP are called DP-complete problems, that can be seen as the conjunction of an NP-complete problem and a co-NP-complete problem. It is easy to see that the problem P vs NP is equivalent to the problem P vs DP, and therefore DP-complete problems would be better candidates to attack the conjecture, since they seem to be harder than NP-complete problems. In this paper, a methodology to transform an efficient solution of an NP-complete problem into an efficient solution of a DP-complete problem is applied. More precisely, a solution to SAT is given by means of a uniform family of recognizer polarizationless P systems with active membranes with dissolution rules and division rules for both elementary and non-elementary membranes, and later it is transformed into a solution to the problem SAT-UNSAT.