يفتقر محتوى هذه المقالة إلى مصادر موثوقة

Co-NP

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

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

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


Nuvola apps edu mathematics-ar.svg
هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. شارك في تحريرها.