المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)

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

تعريف[عدل]

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

امثلة[عدل]

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

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