![](/images/graphics-bg.png)
From NP-Completeness to DP-Completeness: A Membrane Computing Perspective
المؤلفون المشاركون
Valencia-Cabrera, Luis
Pérez-Jiménez, Mario J.
Orellana-Martín, David
Martínez-del-Amor, Miguel Á.
Pérez-Hurtado, Ignacio
المصدر
العدد
المجلد 2020، العدد 2020 (31 ديسمبر/كانون الأول 2020)، ص ص. 1-10، 10ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2020-08-30
دولة النشر
مصر
عدد الصفحات
10
التخصصات الرئيسية
الملخص EN
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.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Valencia-Cabrera, Luis& Orellana-Martín, David& Martínez-del-Amor, Miguel Á.& Pérez-Hurtado, Ignacio& Pérez-Jiménez, Mario J.. 2020. From NP-Completeness to DP-Completeness: A Membrane Computing Perspective. Complexity،Vol. 2020, no. 2020, pp.1-10.
https://search.emarefa.net/detail/BIM-1143343
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Valencia-Cabrera, Luis…[et al.]. From NP-Completeness to DP-Completeness: A Membrane Computing Perspective. Complexity No. 2020 (2020), pp.1-10.
https://search.emarefa.net/detail/BIM-1143343
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Valencia-Cabrera, Luis& Orellana-Martín, David& Martínez-del-Amor, Miguel Á.& Pérez-Hurtado, Ignacio& Pérez-Jiménez, Mario J.. From NP-Completeness to DP-Completeness: A Membrane Computing Perspective. Complexity. 2020. Vol. 2020, no. 2020, pp.1-10.
https://search.emarefa.net/detail/BIM-1143343
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1143343
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
![](/images/ebook-kashef.png)
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر
![](/images/kashef-image.png)