Co-NP
מתוך ויקיפדיה, האנציקלופדיה החופשית
בתורת הסיבוכיות, המחלקה Co-NP הינה המחלקה המשלימה למחלקה NP.
מחלקה זו מכילה את כל הבעיות אשר ניתן לבדוק את שלילתן באופן יעיל.
המחלקה P היא תת-קבוצה הן של NP והן של Co-NP. ההנחה המקובלת היא כי מדובר בהכלה ממש בשני המקרים, וכן כי המחללקות NP וCo-NP אינן שוות. אם זה אכן כך, אף בעיה NP-שלמה אינה נמצאת בCo-NP, ואף בעיה Co-NP-שלמה אינה נמצאת בNP.
ניתן להראות את נכונות הטענה מעלה בצורה הבאה - נניח בשלילה כי קיימת בעיה NP-שלמה אשר שייכת לCo-NP. כיוון שלכל הבעיות במחלקה NP קיימת רדוקציה פולינומית אל הבעיה הNP-שלמה , הרי שלכל בעיה בNP ניתן לבנות מכונה טיורינג אי-דטרמיניסטית אשר מכריעה את הבעיה המשלימה בזמן פולינומי, כלומר NP היא תת-קבוצה של Co-NP. מכאן נובע כי קבוצת הבעיות המשלימות לבעיות בNP היא תת-קבוצה של קבוצת הבעיות המשלימות לבעיות בCo-NP, כלומר Co-NP היא תת-קבוצה בNP. מכאן נובע שNP וCo-NP הן אותה הקבוצה, בסתירה להנחה המקובלת שהן שונות. באופן דומה ניתן להראות את הטענה השנייה (אף בעיה Co-NP-שלמה לא נמצאת בNP).
פרט לכך, אם ניתן להראות שבעיה מסוימת שייכת הן לNP והן לCo-NP, הרי שמקובל להניח כי זוהי ראיה לכך שבעיה זו אינה NP-שלמה. דוגמה אחת היא פירוק לגורמים של מספר שלם, כאשר הבעיה היא זיהוי האם קיים למספר השלם גורם ראשוני הקטן ממספר K נתון. ידוע שבעיה זו אינה בNP ואינה ב־Co-NP, ולכן ההנחה הרווחת כי בעיה זו אינה פולינומית, NP-שלמה או Co-NP-שלמה. הבעיות אשר ניתן לבדוק את שלילתן באופן יעיל.
במשך שנים רבות שימשה דוגמה קלאסית למחלקה זו, בעיית הראשוניות. לא היה ברור מאליו האם ניתן לבדוק באופן יעיל האם מספר הוא ראשוני אולם קל למדי לספק הוכחה שמספר נתון אינו ראשוני: הוכחה כזו צריכה להכיל מחלק אחד של המספר הנתון. כיום כבר ידוע שבעיית הראשוניות (כלומר הכרעה האם מספר נתון הוא ראשוני) היא במחלקה P, ראה http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf#search=%22primes%20is%20in%20p%22

