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 ^[1], ולכן שיערו מאז שהבעיה אינה NP-שלמה. (כיום כבר ידוע שבעיית הראשוניות היא במחלקה P ^[2].)

[עריכה] הערות שוליים

1. ^ ראו הסבר על מאמרו של פרט
2. ^ ראו מאמרם של אגרוול ועמיתיו

]