Article
From SAT to SAT-UNSAT using P systems with dissolution rules
Author/s | Riscos Núñez, Agustín
![]() ![]() ![]() ![]() ![]() ![]() ![]() Valencia Cabrera, Luis ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Publication Date | 2022 |
Deposit Date | 2022-07-01 |
Published in |
|
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 ... 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. |
Funding agencies | Ministerio de Ciencia e Innovación (MICIN). España |
Project ID. | TIN2017-89842-P
![]() |
Citation | 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 |
Files | Size | Format | View | Description |
---|---|---|---|---|
Riscos-Núñez-Valencia-Cabrera2 ... | 1.545Mb | ![]() | View/ | |