مسائل co-NP كاملة
في علم التعقيد الحسابي مسائل co-NP كاملة هي مجموعة جزئية للمجموعة co-NP حيث انه كل أنَّ كل لغة منها يمكن اختصار كل اللغات في co-NP اليها.
تعريف
نقول أن L هي co-NP كاملة إذا Lc تابعة ل-NP كاملة. أي: كل لغة A تابعة ل- co-NP يتحقق التالي: A ≤p L
امثلة
- طوطولوجيا: باعطائنا صيغة بوليانية هل هي صحيحة لكل تعويض في المتغيرات؟
مراجع
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.