co-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.

הערות שוליים


מחלקות חישוביות וסיבוכיות
מקרא
מחלקת חישוביות
מחלקת סיבוכיות
מחלקה המהווה חיתוך של המחלקות שמכילות אותה ומופיעות בתרשים.
מסלול שיורד למטה מצביע על כך שהמחלקה התחתונה היא חלקית ממש למחלקה העליונה
מסלול שיורד למטה מצביע על כך שהמחלקה התחתונה היא חלקית למחלקה העליונה אך לא ידוע האם הן שוות
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

Co-NP41688994Q955748