Co-NP

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

في علم التعقيد الحسابي 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 , باعطائنا مخططان هل هما ليسا متساويا الشكل؟

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

Midori Extension.svg هذه بذرة مقالة تحتاج للنمو والتحسين. ساهم في إثرائها بالمشاركة في تحريرها.