@article {math11132797,
title = {A Protocol for Solutions to DP-Complete Problems through Tissue Membrane Systems},
journal = {Mathematics},
volume = {11},
number = {13},
year = {2023},
month = {06/2023},
pages = {2797},
publisher = {MDPI},
edition = {13},
abstract = {Considering a class\ R\ comprising recognizer membrane systems with the capability of providing polynomial-time and uniform solutions for NP-complete problems (referred to as a \“presumably efficient\” class), the corresponding polynomial-time complexity class PMCR\ encompasses both the NP and\ co-NP\ classes. Specifically, when\ R\ represents the class of recognizer presumably efficient cell-like P systems that incorporate object evolution rules, communication rules, and dissolution rules, PMCR\ includes both the DP and\ co-DP\ classes. Here, DP signifies the class of languages that can be expressed as the difference between any two languages in NP (it is worth noting that NP \⊆ DP and\ co-NP\⊆co-DP). As DP-complete problems are believed to be more complex than NP-complete problems, they serve as promising candidates for studying the P vs. NP problem. This outcome has previously been established within the realm of recognizer P systems with active membranes. In this paper, we extend this result to encompass any class\ R\ of presumably efficient recognizer tissue-like membrane systems by presenting a detailed protocol for transforming solutions of NP-complete problems into solutions of DP-complete problems.},
issn = {2227-7390},
doi = {10.3390/math11132797},
url = {https://www.mdpi.com/2227-7390/11/13/2797},
author = {David Orellana-Mart{\'\i}n and Ram{\'\i}rez-de-Arellano, Antonio and Andreu-Guzm{\'a}n, Jos{\'e} Antonio and {\'A}lvaro Romero-Jim{\'e}nez and Mario J. P{\'e}rez-Jim{\'e}nez}
}