co-NP
 |
בעיות פתוחות במדעי המחשב: האם co-NP = NP?
(בעיות פתוחות נוספות במדעי המחשב) |
בתורת הסיבוכיות, המחלקה co-NP היא המחלקה המשלימה למחלקה NP; כלומר, מחלקה שאיבריה הן בעיות המשלימות לבעיות הנמצאות במחלקה NP.
במילים אחרות: בעוד המחלקה NP מכילה בעיות שניתן לבדוק אישור שלהן בזמן פולינומי, המחלקה 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 [1].)
דוגמה נוספת ויותר מעניינת היא בעיית הפירוק לגורמים: בהינתן שני מספרים טבעיים n, k - האם קיים מספר קטן או שווה ל־k אשר מחלק את n? קל לראות שהבעיה ב-NP, ומכיוון שניתן לבדוק האם מספר הוא ראשוני בסיבוכיות זמן פולינומית - נובע שהבעיה היא גם ב-co-NP, בעיית הפירוק לגורמים מפורסמת בכך שעל הקושי של פתירתה מסתמך פרוטוקול ההצפנה RSA (כלומר, אם בעיית הפירוק לגורמים היא ב-P אזי פרוטוקול RSA לא בטוח לשימוש), עם זאת, סביר להניח כי הבעיה הנ"ל היא לא NP-שלמה שכן היא נמצאת גם ב-NP וגם ב-co-NP.
הערות שוליים
| מחלקות סיבוכיות חשובות (נוספות) | ||
|---|---|---|
| נחשב מעשי | NL • P • ZPP • RP • BPP • BQP • PTAS • APX | |
| ככל הנראה בלתי מעשי | NP • NP-קשיות • co-NP • PP • #P • PSPACE | |
| נחשב כבלתי מעשי | EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL | |
| היררכית מחלקות | ההיררכיה הפולינומית • ההיררכיה האקספוננציאלית • ההיררכיה הבוליאנית • ההיררכיה האריתמטית • היררכית גרזגרצ'יק | |
| משפחות של מחלקות | מערכת הוכחה אינטראקטיבית • DTIME • NTIME • DSPACE • NSPACE | |
28459697Co-NP