מחלקת סיבוכיות NPC
מתוך ויקיפדיה, האנציקלופדיה החופשית
בעייה NP-שלמה (NP-complete באנגלית, או בקיצור NPC) היא בעיית הכרעה השייכת למחלקה NP, ושניתן לבצע רדוקציה פולינומיאלית של כל בעיה אחרת ב-NP אליה (או, במילים אחרות, הבעיה היא NP-קשה). כלומר, קיימת רדוקציה פולינומיאלית מכל בעיה ב-NP אל כל בעיה שהיא NP-קשה.
ביצוע רדוקציה פולינומיאלית מבעיה א' לבעיה ב', פרושו תרגום הקלט של בעיה א' לקלט של בעיה ב', והחזרת הפלט של בעיה ב' בתור הפלט של בעיה א', כך שסיבוכיות פעולת התרגום היא פולינומיאלית באורך הקלט. בדרך זו נקבל כי ניתן לפתור את בעיה א' בעזרת בעיה ב', ושהפרש הזמנים הוא פולינומיאלי לכל היותר.
על מנת להוכיח שבעייה היא NP-שלמה ניתן להראות באופן מפורש רדוקציה מכל בעיה ב-NP אליה (לדוגמה, משפט קוק-לוין מראה זאת עבור בעיית SAT), או להראות רדוקציה מבעיה NP-שלמה אחרת כלשהיא אליה.
ניתן להתייחס לבעיות NP-שלמות בתור הבעיות הקשות ביותר במחלקה NP. זאת מכיוון שאם נפתור (על ידי אלגוריתם) בעיה A בזמן ריצה פולינומיאלי, כאשר A היא בעיה NP-שלמה, נוכיח שלכל בעיה ב-NP יש פתרון פולינומיאלי, שכן מכל בעיה ב-NP יש רדוקציה פולינומיאלית אל A.
במשך שנים נעשה מחקר מעמיק על בעיות אלו, על מנת למצוא להן פתרון פולינומיאלי, או, לחליפין, להוכיח שלא ניתן למצוא פתרון כזה. זאת מכיוון שבהינתן כל אחת משתי אפשרויות אלו, הבעיה הפתוחה במדעי המחשב, "האם P=NP?", תוכרע.
דוגמאות לבעיות שהן NP-שלמות הן בעיית SAT, בעיית הסוכן הנוסע (TSP), מסלול המילטוני, ותכנון לינארי בשלמים. ידועות אלפי בעיות NP-שלמות.
[עריכה] הגדרה פורמלית של NPC
בעיית הכרעה C היא NP-שלמה אם:
ניתן לבצע רדוקציה משמעו כי לכל בעייה L, קיימת פונקציה f לבעייה C הניתנת לחישוב בזמן פולינומיאלי, כך שלכל l ∈ L מתקיים f(l) ∈ C, ולכל l שאינו ב-L לא מתקיים תנאי זה. כדי להוכיח כי C הוא NPC, די לקחת בעייה A שכבר ידוע כי היא ב-NPC ולהראות רדוקציה מ-A ל-C.
המשמעות היא, כי אם יש אלגוריתם פולינומי עבור C, אזי את כל NP ניתן לפתור בזמן פולינומי.
הגדרה זו ניתנה על־ידי סטיבן קוק בשנת 1971, אך הוא לא השתמש בשם זה. שם זה ניתן לו על־ידי ג'ון הופקרופט בשנת 1972 במהלך ויכוח בין מדעני מחשב בקשר לשאלה האם ניתן לפתור בעיות כאלה בזמן פולינומי על־ידי מכונת טיורינג דטרמיניסטית. כולם הגיעו להסכמה שיש לדחות הגעה למסקנה בשאלה לזמן מאוחר יותר, שכן לאף אחד לא הייתה הוכחה פורמלית לכאן או לכאן. שאלה זו הינה P=NP.
איש לא הצליח להוכיח עדיין האם ניתן לפתור בעיות NP-שלמות בזמן פולינומי, וזאת אחת השאלות הפתוחות הגדולות במתמטיקה; מרבית מדעני המחשב חושבים שהתשובה היא שלילית. שאלה זו היא אחת משאלות המליון דולר.
נראה די מפתיע שבעיות NP שלמות קיימות; אך לפי משפט קוק-לוין (שהוכח עצמאית על־ידי ליאונרד לוין), מראה קוק כי בעיית הספיקות של נוסחאות מצורת CNF היא NP-שלמה. בשנת 1972 הוכיח ריצ'רד קארפ כי מספר בעיות אחרות הן NP-שלמות, כך שיש רשימה ארוכה של בעיות כאלה. מאז, עוד אלפי בעיות הוכחו כניתנות לרדוקציה מבעיית SAT.
בעיות שמספקות את תנאי 2, אך לא את תנאי 1, נקראות NP-קשות. בצורה לא פורמלית, בעיות NP-קשות הן קשות לפחות כמו בעייה NP-שלמה כלשהי.
[עריכה] רשימת 21 בעיות NP-שלמות של קארפ
- בעיית SAT
- בעיית תת-גרף מלא (ראו גם קבוצת קודקודים בלתי תלויה)
- בעיית תת-קבוצות זרות - בהינתן תת קבוצות של קבוצה מסוימת, האם יש k קבוצות זרות?
- בעיית כיסוי קודקודים (VC) - בהינתן גרף, האם יש k קודקודים שמכסים את כל הקשתות?
- בעיית כיסוי קבוצות - בהינתן תתי קבוצות של קבוצה נתונה, האם יש k קבוצות שאיחודן הוא כל הקבוצה?
- בעיית FAS - בהינתן גרף מכוון, האם ניתן לקבל גרף ללא מעגלים על ידי הוצאת k קשתות לכל היותר?
- בעיית FVS - בהינתן גרף לא מכוון, האם ניתן לקבל גרף ללא מעגלים על ידי הוצאת k קודוקדים לכל היותר?
- מסלול המילטוני מכוון - בהינתן גרף מכוון, האם יש בו מסלול המילטוני?
- מסלול המילטוני לא מכוון - בהינתן גרף לא מכוון, האם יש בו מסלול המילטוני?
- תכנון לינארי בשלמים - בהינתן מערכת אי שוויונות, האם יש פתרון שבו כל המשתנים מקבלים ערכים שלמים?
- בעיית 3SAT - בהינתן נוסחת CNF בו בכל קלוז יש 3 משתנים, האם הוא ניתן לסיפוק?
- צביעת גרף - בהינתן גרף, האם ניתן לצבוע אותו ב-k צבעים, כאשר כל קשת מחברת בין קודקודים שאינם מאותו צבע?
- כיסוי קליקים - בהינתן גרף, האם ניתן לכסות את כל הקשתות שלו בעזרת k קליקים?
- כיסוי מדויק - בהינתן תתי-קבוצות של קבוצה, האם ניתן למצוא קבוצות זרות שאיחודן הוא כל הקבוצה?
- התאמה 3-ממדים (3DM) - בהינתן 3 קבוצות בגודל n, וקבוצות שלשות כך שהאיבר הראשון נמצא בקבוצה הראשונה וכו', האם קיימת קבוצה של n שלשות שמכסות את כל הקבוצות?
- עץ סטיינר - בהינתן n נקודות במישור, האם ניתן לחבר אותם בעזרת קטעים שסכום האורכים קטן מ-k?
- בעיית Hitting Set (HS) - בהינתן קבוצה של קבוצות, האם קיימת קבוצה שאיננה גדולה מ-k שיש בה לפחות איבר אחד מכל קבוצה?
- בעיית Knapsack (KN) - בהינתן קבוצת איברים והגדלים שלהם, ותרמיל בגודל נתון, האם ניתן למצוא קבוצת איברים בגודל כולל של לפחות k שניתן להכניס את כולם לתרמיל?
- סידור משימות - בהינתן קבוצת משימות, כל אחד ופרק הזמן שלוקח לבצע אותו, האם ניתן לבצע את כולם תוך k זמן על n מחשבים?
- בעיית החלוקה (PAR) - בהינתן קבוצת מספרים, האם ניתן לחלק אותם לשני קבוצות, שסכום כל אחד מהם שווה?
- בעיית הפרדה מקסימלית - בהינתן גרף ממושקל, האם ניתן למצוא חלוקה של הגרף לשני קבוצות, כך שסכום משקלי הקשתות שמחברות ביניהם הוא לפחות k?
- צביעת גרף - בהינתן גרף, האם ניתן לצבוע אותו ב-k צבעים, כאשר כל קשת מחברת בין קודקודים שאינם מאותו צבע?
- בעיית תת-גרף מלא (ראו גם קבוצת קודקודים בלתי תלויה)
[עריכה] דוגמאות נוספות
דוגמה מעניינת היא בעיית האיזומורפיזם של גרפים. גרפים נחשבים איזומורפיים אם ניתן להגיע מאחד לשני על־ידי שינוי שמות הקודקודים. נשווה בין שתי הבעיות הבאות:
- איזומורפיזם גרפים - האם G1 איזומורפי ל־G2?
- איזומורפיזם תת-גרפי - האם G1 איזומורפי לתת-גרף של G2?
הבעייה השנייה היא NP-שלמה. כיום מדעני המחשב חושבים כי הבעייה הראשונה היא לא ב־P ולא ב־NPC, אך ברור שהיא ב־NP. זאת דוגמה של בעייה שחושבים שהיא קשה, אך לא חושבים שהיא NP-שלמה.
חלק ניכר מבעיות NPC ניתן לפתור בזמן פולינומי אם מניחים אילוצים שונים (לדוגמה, בעיית 2SAT ניתן לפתרון בזמן פולינומי), וחלקם ניתנים לקירוב (לבעיית Knapsack ניתן לקרב עד כדי 50%).

