ROMJIST Volume 21, No. 3, 2018, pp. 288-297
D. Orellana-Martin, L. Valencia-Cabrera, A. Riscos-Nunez, M. J. Perez-Jimenez The Unique Satisfiability Problem from a Membrane Computing Perspective
ABSTRACT: Complexity class DP is the class of “differences” of any two languages in NP. It verifies that NP ∪ co-NP ⊆ DP ⊆P^NP, where P^NP is the second level of the polynomial hierarchy, specifically, it is the class of languages decidable by a deterministic polynomial-time Turing machine having access to an NP oracle. The unique sastifiability problem (UNIQUE SAT) is a well known DP problem which has been proved to be co-NPhard. In this paper, a uniform and polynomial time solution for the UNIQUE SAT problem is given by a family of polarizationless P systems with active membranes and division rules only for elementary membranes, without dissolution rules but using minimal cooperation and minimal production in object evolution rules.KEYWORDS: Complexity class DP; polarizationless P systems with active membranes; cooperative rules; UNIQUE SAT problemRead full text (pdf)