|
'''לדוגמה:''' [[בעיית הסכומים החלקיים|בעיית סכום תת-קבוצה]] היא '''בעיית NP'''. הגדרתה היא: נתונה קבוצה סופית של מספרים שלמים. האם קיימת לקבוצה זו תת-קבוצה, כך שסכום כל איבריה הוא אפס? תשובה מאשרת כלשהי לשאלה זו היא רשימת איברים שתומכים בטענה (סכומם אפס). תשובה זו '''ניתנת לבדיקה''' בזמן פולינומי – סכימת האיברים והשוואת הסכום לאפס.
'''בעיית הcoה־co-NP המשלימה לה''' היא: נתונה קבוצה סופית של מספרים שלמים. האם סכום איברי כל תת-קבוצה שונה מאפס? תשובה שוללת לשאלה זו היא רשימת איברים השוללים את הטענה (סכומם אפס). גם דבר זה בדיק בזמן פולינומי – סכימת האיברים והשוואת הסכום לאפס.
המחלקה [[P (מדעי המחשב)|P]] היא תת-קבוצה הן של NP והן של co-NP. ההנחה המקובלת היא כי מדובר בהכלה ממש בשני המקרים, וכן כי המחלקות NP וcoו־co-NP אינן שוות. אם זה אכן כך, אף בעיה [[NP-שלמה]] אינה נמצאת ב-co-NP, ואף בעיה co-NP-שלמה אינה נמצאת בNPב־NP.
ניתן להראות את נכונות הטענה בצורה הבאה - [[הוכחה בדרך השלילה|נניח בשלילה]] כי קיימת בעיה NP-שלמה אשר שייכת לcoל־co-NP. כיוון שלכל הבעיות במחלקה NP קיימת [[רדוקציה פולינומית]] אל הבעיה הNPה־NP-שלמה, הרי שלכל בעיה בNPב־NP ניתן לבנות מכונה טיורינג אי-דטרמיניסטית אשר מכריעה את הבעיה המשלימה בזמן פולינומי, כלומר NP היא תת-קבוצה של co-NP. מכאן נובע כי קבוצת הבעיות המשלימות לבעיות בNPב־NP היא תת-קבוצה של קבוצת הבעיות המשלימות לבעיות בcoב־co-NP, כלומר co-NP היא תת-קבוצה בNPב־NP. מכאן נובע שNPש־NP וcoו־co-NP הן אותה הקבוצה, בסתירה להנחה המקובלת שהן שונות. באופן דומה ניתן להראות את הטענה השנייה (אף בעיה co-NP-שלמה לא נמצאת בNPב־NP).
אי לכך, אם ניתן להראות שבעיה מסוימת שייכת הן לNPל־NP והן לcoל־co-NP, הרי שמקובל להניח כי זוהי ראיה לכך שבעיה זו אינה NP-שלמה. כך למשל, לגבי בעיית הראשוניות - האם מספר נתון הוא [[ראשוני]] - קל לראות שהבעיה ב־co-NP. ההוכחה שמספר אינו ראשוני הוא פשוט מספר אחר שונה מאחד ש[[מחלק]] אותו. ב-1975 הראה וון פרט כי הבעיה היא ב־NP, ולכן שיערו מאז שהבעיה אינה NP-שלמה. (כיום כבר ידוע שבעיית הראשוניות היא במחלקה [[P (סיבוכיות)|P]] {{כ}}{{הערה|1=ראו [http://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf מאמרם של אגרוול ועמיתיו]}}.)
דוגמה נוספת ויותר מעניינת היא בעיית הפירוק לגורמים: בהינתן שני מספרים טבעיים n, k - האם קיים מספר קטן או שווה לkל־k אשר מחלק את n? קל לראות שהבעיה ב-NP, ומכיוון שניתן לבדוק האם מספר הוא ראשוני בסיבוכיות זמן פולינומית - נובע שהבעיה היא גם ב-co-NP, בעיית הפירוק לגורמים מפורסמת בכך שעל הקושי של פתירתה מסתמך פרוטוקול ההצפנה RSA (כלומר, אם בעיית הפירוק לגורמים היא ב-P אזי פרוטוקול RSA לא בטוח לשימוש), עם זאת, סביר להניח כי הבעיה הנ"ל היא לא NP-שלמה שכן היא נמצאת גם ב-NP וגם ב-co-NP.
== הערות שוליים ==
| 