كو-إن بي

في علم التعقيد الحسابي co-NP هي المجموعة المُكملة ل-NP أي: co-NP={0,1}* \ NP .
 تعريف 
نقول أنَّ اللغة L تابعة ل- co-NP إذا:

يوجد آلة تيورنج M بحيث أنّ وقتها حدودي ويتحقق التالي: x ∈ L ⇔ ∀ q ∈ {0,1}poly(|x|) M(x,q)=1

في حين أنَّ |x| هو طول المُدخل x .
 علاقات مع اقسام أخرى 
 معلوم انَّ P ⊆ co-NP
 في حين انه غير معلوم العلاقة بين NP و- co-NP معظم علماء الحاسوب يؤمنون بشدة: co-NP ≠ NP
 co-RP ⊆ co-NP
 امثلة 
 طوطولوجيا: باعطائنا صيغة بوليانية هل هي صحيحة لكل تعويض في المتغيرات؟
 كما اوردنا سالفا كل مسألة في NP المُكمل لها في co-NP .
 مسألة GNI , باعطائنا مخططان هل هما ليسا متساويا الشكل؟

 مراجع 

 انظر أيضا 
 قسم تعقيد
 نظرية التعقيد الحسابي.
 مسألة P=NP
 خوارزمية

تصنيف:أقسام التعقيد الحسابي
تصنيف:علم الحاسوب النظري