A Protocol for Solutions to DP-Complete Problems through Tissue Membrane Systems

David Orellana-Martín (), Antonio Ramírez- de-Arellano, José Antonio Andreu-Guzmán, Álvaro Romero-Jiménez and Mario J. Pérez-Jiménez
Additional contact information
David Orellana-Martín: Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
Antonio Ramírez- de-Arellano: Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
José Antonio Andreu-Guzmán: Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
Álvaro Romero-Jiménez: Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
Mario J. Pérez-Jiménez: Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

Mathematics, 2023, vol. 11, issue 13, 1-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 PMC R 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, PMC R 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.

Keywords: complexity class; DP; membrane computing; tissue P systems (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/13/2797/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/13/2797/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:13:p:2797-:d:1176368

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().