כל מה שרצית לדעת על co-NP:
לדוגמה: בעיית סכום תת-סדרה היא בעיית NP.
הגדרתה היא: נתונה סדרה סופית של מספרים שלמים.
האם קיימת לסדרה זו תת-סדרה, כך שסכום כל איבריה הוא אפס? תשובה מאשרת כלשהי לשאלה זו היא רשימת איברים שתומכים בטענה (סכומם אפס).
תשובה זו ניתנת לבדיקה בזמן פולינומי – סכימת האיברים והשוואת הסכום לאפס.
בעיית הco-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-שלמה.
כך למשל, לגבי בעיית הראשוניות – האם מספר נתון הוא ראשוני – קל לראות שהבעיה ב־co-NP.
ההוכחה שמספר אינו ראשוני הוא פשוט מספר אחר שונה מאחד שמחלק אותו.
ב-1975 הראה וון פרט כי הבעיה היא ב־NP, ולכן שיערו מאז שהבעיה אינה NP-שלמה.
(כיום כבר ידוע שבעיית הראשוניות היא במחלקה P .
)
נלקח מויקיפדיה