co-NP

في نظرية التعقيد الحسابي ، تُعدّ co-NP فئة تعقيد . تنتمي مسألة القرار X إلى co-NP إذا وفقط إذا كان مكملها X ينتمي إلى فئة التعقيد NP . يمكن تعريف هذه الفئة كما يلي: تنتمي مسألة القرار إلى co-NP إذا وفقط إذا كان لكل حالة من حالات no- ، لدينا " شهادة " ذات طول متعدد الحدود، وهناك خوارزمية ذات زمن متعدد الحدود يمكن استخدامها للتحقق من أي شهادة مزعومة.

أي أن co-NP هي مجموعة مسائل القرار التي يوجد فيها متعدد الحدود ⁠${\displaystyle p(n)}$وآلة تورينج محدودة الوقت متعدد الحدود M بحيث يكون لكل حالة x ، x حالة لا شيء إذا وفقط إذا: لبعض الشهادات الممكنة c ذات الطول المحدود بـ${\displaystyle p(n)}$تقبل آلة ^تورينج M الزوج ( x ، c ) . [ ^{1 ]}

بينما تسأل مسألة NP عما إذا كانت حالة معينة حالة "نعم" ، فإن مكملتها تسأل عما إذا كانت حالة معينة حالة "لا" ، مما يعني أن المكمل يقع في فئة co-NP. أي حالة "نعم" في مسألة NP الأصلية تصبح حالة "لا" في مكملتها، والعكس صحيح.

تكون المسألة L كاملة من نوع co-NP إذا وفقط إذا كانت L في co-NP، ولأي مسألة في co-NP، يوجد اختزال زمني متعدد الحدود من تلك المسألة إلى L.

مشكلة لم تُحل في علوم الحاسوب

⁠${\displaystyle {\textsf {NP}}\ {\overset {?}{=}}\ {\textsf {co-NP}}}$⁠

المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

تُعدّ P ، وهي فئة المسائل القابلة للحل في زمن متعدد الحدود، مجموعة جزئية من كلٍّ من NP و co-NP. ويُعتقد أن P مجموعة جزئية صارمة في كلتا الحالتين. ولأن P مغلقة تحت التتميم، ولأن NP و co-NP متكاملتان، فلا يمكن أن تكون صارمة في حالة وغير صارمة في الأخرى: إذا كانت P تساوي NP، فيجب أن تساوي co-NP أيضًا، والعكس صحيح. ^{[ 2 ]}

يُعتقد أيضًا أن NP و co-NP غير متساويتين، ^{[ 3 ]} وأن تساويهما يعني انهيار التسلسل الهرمي متعدد الحدود PH إلى NP. إذا كانتا غير متساويتين، فلا يمكن أن تكون أي مسألة NP-كاملة ضمن co-NP، ولا يمكن أن تكون أي مسألة co-NP-كاملة ضمن NP. ^{[ 4 ]} يمكن إثبات ذلك كما يلي: لنفترض جدلاً وجود مسألة NP-كاملة X ضمن co-NP. بما أن جميع المسائل في NP يمكن اختزالها إلى X ، فإنه يترتب على ذلك أنه لكل مسألة في NP، يمكننا بناء آلة تورينغ غير حتمية تُحدد مكملتها في وقت متعدد الحدود؛ أي ،${\displaystyle {\textsf {NP}}\subseteq {\textsf {co-NP}}}$ومن هذا، يتبين أن مجموعة مكملات المسائل في فئة NP هي مجموعة جزئية من مجموعة مكملات المسائل في فئة co-NP ؛ أي${\displaystyle {\textsf {co-NP}}\subseteq {\textsf {NP}}}$وهكذا​​${\displaystyle {\textsf {co-NP}}={\textsf {NP}}}$. البرهان على أنه لا يمكن أن تكون أي مسألة كاملة مشتركة من فئة NP ضمن فئة NP إذا ⁠${\displaystyle {\textsf {NP}}\neq {\textsf {co-NP}}}$متناظر .

co-NP هي مجموعة فرعية من PH ، والتي هي بدورها مجموعة فرعية من PSPACE .

• حديقة حيوانات التعقيد : coNP