كو-إن بي
باختصار: في علم التعقيد الحسابي co-NP هي المجموعة المُكملة ل-NP أي: co-NP={0,1}* \ NP . في هذه المقالة 4 أقسام: «امثلة»، «تعريف» و«معلوم انَّ P ⊆ co-NP» وغيرها.
تعريفًا بالموضوع، في علم التعقيد الحسابي co-NP هي المجموعة المُكملة ل-NP أي: co-NP={0,1}* \ NP . وتعرض الأقسام التالية جوانب أخرى من الموضوع.
امثلة
- طوطولوجيا: باعطائنا صيغة بوليانية هل هي صحيحة لكل تعويض في المتغيرات؟
- كما اوردنا سالفا كل مسألة في NP المُكمل لها في co-NP .
- مسألة GNI , باعطائنا مخططان هل هما ليسا متساويا الشكل؟
- مراجع
- انظر كذلك
تعريف
- نقول أنَّ اللغة L تابعة ل- co-NP إذا:
- في حين أنَّ |x| هو طول المُدخل x .
- علاقات مع اقسام أخرى
معلوم انَّ P ⊆ co-NP
co-RP ⊆ co-NP
ومن جهة أخرى، في حين انه غير معلوم العلاقة بين NP و- co-NP أغلب علماء الحاسوب يؤمنون بشدة: co-NP ≠ NP
قسم تعقيد
مسألة P=NP
نظرية التعقيد الحسابي.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟