מחלקת הסיבוכיות 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-שלמה אם:

1. היא נמצאת ב-NP
2. היא NP-קשה, כלומר ניתן לבצע רדוקציה מכל בעיית 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?

[עריכה] דוגמאות נוספות

דוגמה מעניינת היא בעיית האיזומורפיזם של גרפים. גרפים נחשבים איזומורפיים אם ניתן להגיע מאחד לשני על ידי שינוי שמות הקודקודים. נשווה בין שתי הבעיות הבאות:

• איזומורפיזם גרפים - האם G₁ איזומורפי ל־G₂?
• איזומורפיזם תת-גרפי - האם G₁ איזומורפי לתת-גרף של G₂?

הבעיה השנייה היא NP-שלמה (לדוגמה כי קל לנסח את שאלת המסלול המילטוני לא מכוון כך). לעומת זאת בעיית האיזומורפיזם של גרפים היא דוגמה לבעיה ב-NP שלא ידוע לגביה אם היא ב־P או אם היא NP-שלמה. ניתן להראות כי אם היא NP-שלמה אז מבנה מחלקות הסיבוכיות שונה מההשערות המקובלות ובפרט כי ההיררכיה הפולינומית מתמוטטת.

חלק ניכר מבעיות NPC ניתן לפתור בזמן פולינומי אם מניחים אילוצים שונים (לדוגמה, בעיית 2SAT ניתן לפתרון בזמן פולינומי), וחלקם ניתנים לקירוב (בעיית Knapsack ניתנת לקירוב עד כדי כל קבוע גדול מ-1).