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.

הערות שוליים

1. ראו מאמרם של אגרוול ועמיתיו