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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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

تعريف[عدل]

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

امثلة[عدل]

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

أنظر أيضا[عدل]