انتقل إلى المحتوى

مسائل co-NP كاملة

يفتقر محتوى هذه المقالة إلى مصادر موثوقة.
يرجى إضافة قالب معلومات متعلّقة بموضوع المقالة.
من ويكيبيديا، الموسوعة الحرة

في علم التعقيد الحسابي مسائل co-NP كاملة هي مجموعة جزئية للمجموعة co-NP حيث انه كل أنَّ كل لغة منها يمكن اختصار كل اللغات في co-NP اليها.

تعريف

[عدل]

نقول أن L هي co-NP كاملة إذا Lc تابعة ل-NP كاملة. أي: كل لغة A تابعة ل- co-NP يتحقق التالي: A ≤p L

امثلة

[عدل]
  • طوطولوجيا: باعطائنا صيغة بوليانية هل هي صحيحة لكل تعويض في المتغيرات؟

مراجع

[عدل]

انظر أيضا

[عدل]