Artículo
From SAT to SAT-UNSAT using P systems with dissolution rules
Autor/es | Riscos Núñez, Agustín
Valencia Cabrera, Luis |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2022 |
Fecha de depósito | 2022-07-01 |
Publicado en |
|
Resumen | 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 ... 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. |
Agencias financiadoras | Ministerio de Ciencia e Innovación (MICIN). España |
Identificador del proyecto | TIN2017-89842-P |
Cita | Riscos Núñez, A. y Valencia Cabrera, L. (2022). From SAT to SAT-UNSAT using P systems with dissolution rules. Journal of membrane computing, April 2022 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Riscos-Núñez-Valencia-Cabrera2 ... | 1.545Mb | [PDF] | Ver/ | |