מודלים חישוביים — מרחב למידה אישי

ברוכים הבאים ליחידה "שלמות NP ורדוקציות פולינומיות" בקורס "מודלים חישוביים". יחידה זו עוסקת באחד האתגרים המרכזיים במדעי המחשב התיאורטיים: זיהוי וסיווג הבעיות החישוביות הקשות ביותר, וכיצד אנו יכולים להוכיח שבעיה מסוימת היא אכן "קשה" במובן פורמלי. נלמד על מחלקות הסיבוכיות P ו-NP, על מושג הרדוקציה הפולינומית, ועל המעמד המיוחד של בעיות NP-שלמות, שהן הבעיות ה"קשות ביותר" במחלקת NP.

מחלקות הסיבוכיות P ו-NP

כדי להבין את מושג שלמות NP, עלינו תחילה להגדיר את מחלקות הסיבוכיות הבסיסיות P ו-NP, המהוות את עמוד השדרה של תורת הסיבוכיות החישובית.

בעיית הכרעה: בעיה שמטרתה להחזיר "כן" או "לא" עבור קלט נתון. רוב הדיון ב-NP-שלמות מתמקד בבעיות הכרעה.

מחלקת P

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

מחלקת NP

מחלקת כל בעיות ההכרעה שפתרונן (אם קיים) ניתן לאימות על ידי אלגוריתם דטרמיניסטי בזמן פולינומי. כלומר, אם מישהו נותן לנו "הוכחה" או "עדות" לפתרון, אנו יכולים לבדוק את נכונותה ביעילות.

הקשר בין P ל-NP

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

רדוקציות פולינומיות

רדוקציות הן הכלי המרכזי להשוואת קושי של בעיות. רדוקציה מבעיה A לבעיה B פירושה שאם יש לנו פותר יעיל ל-B, נוכל להשתמש בו כדי לפתור את A ביעילות.

רדוקציה (כללית): טרנספורמציה של מופע של בעיה אחת (A) למופע של בעיה אחרת (B), כך שפתרון המופע של B יכול לשמש לפתרון המופע המקורי של A.

רדוקציה פולינומית (Karp Reduction): רדוקציה מבעיה A לבעיה B, שבה הטרנספורמציה של הקלט מ-A ל-B מתבצעת בזמן פולינומי, וגם הטרנספורמציה של הפתרון מ-B ל-A (אם נדרשת) מתבצעת בזמן פולינומי. מסמנים A ≤_P B.

חשיבותן של רדוקציות פולינומיות

אם A ≤_P B ו-B ∈ P, אז A ∈ P. (כלומר, אם B קלה, ו-A ניתנת לרדוקציה אליה ביעילות, אז גם A קלה).
אם A ≤_P B ו-A ∉ P, אז B ∉ P. (כלומר, אם A קשה, ו-A ניתנת לרדוקציה אליה ביעילות, אז גם B קשה).
רדוקציות מאפשרות לנו לבנות "שרשרת קושי" בין בעיות.

שלמות NP

מושג שלמות NP מגדיר את הבעיות "הקשות ביותר" במחלקת NP. אלו בעיות שכל בעיה אחרת ב-NP ניתנת לרדוקציה פולינומית אליהן.

NP-קשה (NP-Hard): בעיה H היא NP-קשה אם לכל בעיה L ∈ NP מתקיים L ≤_P H. כלומר, H קשה לפחות כמו כל בעיה אחרת ב-NP.

NP-שלמה (NP-Complete): בעיה C היא NP-שלמה אם היא מקיימת שני תנאים:

C ∈ NP (הפתרון שלה ניתן לאימות בזמן פולינומי).
C היא NP-קשה (כל בעיה ב-NP ניתנת לרדוקציה פולינומית אליה).

הוכחת NP-שלמות: זוהי אחת המשימות המרכזיות והנפוצות ביותר במבחנים. כדי להוכיח שבעיה חדשה L היא NP-שלמה, יש לבצע שני שלבים:

הוכחה ש-L ∈ NP: יש להראות שבהינתן "הצעה לפתרון" (witness/certificate) עבור מופע של L, ניתן לאמת את נכונותה בזמן פולינומי.
הוכחה ש-L היא NP-קשה: יש לבחור בעיה קיימת וידועה שהיא NP-שלמה (למשל SAT, 3-SAT, CLIQUE, VERTEX-COVER) ולהראות שניתן לבצע רדוקציה פולינומית ממנה ל-L. כלומר, להראות ש-K ≤_P L, כאשר K היא בעיה NP-שלמה ידועה.

השלב השני הוא לרוב המאתגר יותר ודורש יצירתיות בבניית פונקציית הטרנספורמציה.

משפט קוק-לוין (Cook-Levin Theorem)

משפט קוק-לוין הוא אבן יסוד בתורת הסיבוכיות. הוא קובע כי בעיית הספיקות הבוליאנית (SAT) היא NP-שלמה. זהו המשפט הראשון שהוכיח קיום של בעיה NP-שלמה, ומהווה את נקודת המוצא לכל שרשרת הרדוקציות שבאמצעותה אנו מוכיחים שבעיות רבות אחרות הן NP-שלמות.

דוגמאות לבעיות NP-שלמות

קיימות אלפי בעיות NP-שלמות בתחומים שונים של מדעי המחשב, הנדסה, אופטימיזציה ועוד. הנה כמה מהן, הנחשבות קנוניות:

SAT (Satisfiability): בהינתן נוסחה בוליאנית, האם קיימת השמה למשתנים כך שהנוסחה תקבל ערך "אמת"?
3-SAT: מקרה פרטי של SAT שבו הנוסחה היא בצורת CNF (צורה נורמלית קוניונקטיבית) וכל פסוקית מכילה בדיוק שלושה ליטרלים.
CLIQUE: בהינתן גרף G ומספר k, האם קיים תת-גרף מלא (קליקה) בגודל k ב-G?
VERTEX-COVER: בהינתן גרף G ומספר k, האם קיים קבוצת קודקודים בגודל k כך שכל קשת ב-G נוגעת בלפחות אחד מהם?
HAMILTONIAN-CYCLE: בהינתן גרף G, האם קיים מסלול המילטוני (מסלול פשוט העובר בכל קודקוד בדיוק פעם אחת וחוזר לנקודת ההתחלה)?
SUBSET-SUM: בהינתן קבוצת מספרים שלמים S ומספר יעד T, האם קיימת תת-קבוצה של S שסכום איבריה שווה ל-T?

שאלות לדיון

הסבירו במילים שלכם את ההבדל המהותי בין מחלקת P למחלקת NP. מדוע השאלה P=NP כה חשובה?
תארו את שני השלבים הנדרשים להוכחת NP-שלמות של בעיה חדשה L. מדוע כל אחד מהשלבים הכרחי?
בחרו שתי בעיות NP-שלמות שונות (למשל CLIQUE ו-VERTEX-COVER) והסבירו בקצרה את מהותן. מה הופך אותן ל"קשות"?
האם בעיה שהיא NP-קשה חייבת להיות גם ב-NP? נמקו.

נקודות לתשובת מודל

P vs. NP: P - פתרון יעיל (זמן פולינומי) דטרמיניסטי. NP - אימות יעיל (זמן פולינומי) דטרמיניסטי של פתרון מוצע. P=NP משמעותו שכל בעיה שניתן לאמת את פתרונה ביעילות, גם ניתנת לפתרון ביעילות.
הוכחת NP-שלמות:
1. L ∈ NP: הצגת אלגוריתם אימות דטרמיניסטי בזמן פולינומי שמקבל קלט ו"עדות" ובודק את נכונות העדות ביחס לקלט.
2. L היא NP-קשה: בחירת בעיה K ידועה כ-NP-שלמה. בניית פונקציית רדוקציה f שמעבירה מופע של K למופע של L בזמן פולינומי, כך שמופע K הוא "כן" אם ורק אם מופע L הוא "כן".
בעיות NP-שלמות: CLIQUE - מציאת תת-גרף מלא בגודל נתון. VERTEX-COVER - מציאת קבוצת קודקודים מינימלית שמכסה את כל הקשתות. קושי נובע מהצורך לבדוק מספר אקספוננציאלי של אפשרויות.
NP-קשה ו-NP: לא בהכרח. בעיה יכולה להיות NP-קשה אך לא ב-NP (למשל בעיית העצירה, שהיא לא כריעה כלל, או בעיות במחלקות גבוהות יותר בהיררכיה הפולינומית). התנאי השני להגדרת NP-שלמות הוא שהבעיה תהיה גם ב-NP.

מצאתם טעות או שחסר משהו?