Artículo
The Unique Satisfiability Problem from a Membrane Computing Perspective
Autor/es | Orellana Martín, David
Valencia Cabrera, Luis Riscos Núñez, Agustín Pérez Jiménez, Mario de Jesús |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2018 |
Fecha de depósito | 2021-04-26 |
Publicado en |
|
Resumen | Complexity class DP is the class of “differences” of any two languages in
NP. It verifies that NP[ co-NP DP PNP, where PNP is the second level of the
polynomial hierarchy, specifically, it is the class of languages ... Complexity class DP is the class of “differences” of any two languages in NP. It verifies that NP[ co-NP DP PNP, where PNP 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. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España National Natural Science Foundation of China |
Identificador del proyecto | TIN2017-89842-P
nº 61320106005 |
Cita | Orellana Martín, D., Valencia Cabrera, L., Riscos Núñez, A. y Pérez Jiménez, M.d.J. (2018). The Unique Satisfiability Problem from a Membrane Computing Perspective. Romanian Journal of Information Science and Technology (ROMJIST), 21 (3), 288-297. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
The Unique Satisfiability Problem ... | 241.5Kb | [PDF] | Ver/ | |