Romanian Journal of Information Science and Technology (ROMJIST)

An open – access publication

  |  HOME  |   GENERAL INFORMATION  |   ROMJIST ON-LINE  |  KEYINFORMATION FOR AUTHORS  |   COMMITTEES  |  

ROMJIST is a publication of Romanian Academy,
Section for Information Science and Technology

Editor – in – Chief:
Academician Dan Dascalu

Secretariate (office):
Adriana Neagu
Adress for correspondence: romjist@romjist.ro

Editing of the printed version: Mihaela Marian (Publishing House of the Romanian Academy, Bucharest)

Sponsor: National Institute
for R & D in Microtechnology
(IMT Bucharest)

ROMJIST Volume 21, No. 3, 2018, pp. 288-297, Paper no. 601/2018
 

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 problem

Read full text (pdf)






  |  HOME  |   GENERAL INFORMATION  |   ROMJIST ON-LINE  |  KEYINFORMATION FOR AUTHORS  |   COMMITTEES  |