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"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر