Academic Journal
From NP-Completeness to DP-Completeness: A Membrane Computing Perspective
| العنوان: | From NP-Completeness to DP-Completeness: A Membrane Computing Perspective |
|---|---|
| المؤلفون: | Luis Valencia-Cabrera, David Orellana-Martín, Miguel Á. Martínez-del-Amor, Ignacio Pérez-Hurtado, Mario J. Pérez-Jiménez |
| المصدر: | Complexity, Vol 2020 (2020) |
| بيانات النشر: | Hindawi-Wiley |
| سنة النشر: | 2020 |
| المجموعة: | Directory of Open Access Journals: DOAJ Articles |
| مصطلحات موضوعية: | Electronic computers. Computer science, QA75.5-76.95 |
| الوصف: | Presumably efficient computing models are characterized by their capability to provide polynomial-time solutions for NP-complete problems. Given a class ℛ of recognizer membrane systems, ℛ denotes the set of decision problems solvable by families from ℛ in polynomial time and in a uniform way. PMCℛ is closed under complement and under polynomial-time reduction. Therefore, if ℛ is a presumably efficient computing model of recognizer membrane systems, then NP ∪ co-NP ⊆ PMCℛ. In this paper, the lower bound NP ∪ co-NP for the time complexity class PMCℛ is improved for any presumably efficient computing model ℛ of recognizer membrane systems verifying some simple requirements. Specifically, it is shown that DP ∪ co-DP is a lower bound for such PMCℛ, where DP is the class of differences of any two languages in NP. Since NP ∪ co-NP ⊆ DP ∩ co-DP, this lower bound for PMCℛ delimits a thinner frontier than that with NP ∪ co-NP. |
| نوع الوثيقة: | article in journal/newspaper |
| اللغة: | English |
| Relation: | http://dx.doi.org/10.1155/2020/6765097; https://doaj.org/toc/1076-2787; https://doaj.org/toc/1099-0526; https://doaj.org/article/b4818bce4dc344518deae5cec7ef020f |
| DOI: | 10.1155/2020/6765097 |
| الاتاحة: | https://doi.org/10.1155/2020/6765097 https://doaj.org/article/b4818bce4dc344518deae5cec7ef020f |
| رقم الانضمام: | edsbas.58C8693B |
| قاعدة البيانات: | BASE |
| DOI: | 10.1155/2020/6765097 |
|---|