%0 Generic
%D 2023
%T A Protocol for Solutions to DP-Complete Problems through Tissue Membrane Systems
%A David Orellana-Martín
%A Ramírez-de-Arellano, Antonio
%A Andreu-Guzmán, José Antonio
%A Álvaro Romero-Jiménez
%A Mario J. Pérez-Jiménez
%I MDPI
%P 2797
%R 10.3390/math11132797
%U https://www.mdpi.com/2227-7390/11/13/2797
%V 11
%X 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.
%7 13
%8 06/2023