مسائل co-NP كاملة
باختصار: في علم التعقيد الحسابي مسائل co-NP كاملة هي مجموعة جزئية للمجموعة co-NP حيث انه كل أنَّ كل لغة منها يمكن اختصار كل اللغات في co-NP اليها. في هذه المقالة 3 أقسام: «قسم تعقيد»، «تعريف» و«امثلة».
في البداية، في علم التعقيد الحسابي مسائل co-NP كاملة هي مجموعة جزئية للمجموعة co-NP حيث انه كل أنَّ كل لغة منها يمكن اختصار كل اللغات في co-NP اليها. ونتناول فيما يلي مزيدًا من التفاصيل.
قسم تعقيد
مسألة P=NP
نظرية التعقيد الحسابي.
تعريف
وفي السياق ذاته، نقول أن L هي co-NP كاملة إذا Lc تابعة ل-NP كاملة. أي: كل لغة A تابعة ل- co-NP يتحقق التالي: A ≤p L
امثلة
- طوطولوجيا: باعطائنا صيغة بوليانية هل هي صحيحة لكل تعويض في المتغيرات؟
- مراجع
- انظر كذلك
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟