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].)

הערות שוליים[עריכת קוד מקור | עריכה]