מפת הסיבוכיות
EN
A ≤p B

אוסף הרדוקציות

כל רדוקציה שהקורס ביצע — 28 בסך הכול, 26 רדוקציות קארפ ו-2 חסמי אי-קירוב — עם הבנייה, שני כיווני הוכחת הנכונות, וסיבוכיות הזמן והמקום של הרדוקציה עצמה. החץ מצביע מהבעיה שכבר ידועה כקשה אל הבעיה שאותה רוצים להוכיח כקשה.

28רדוקציות
27עם המחשה
2חסמי אי-קירוב
0מחוץ לקורפוס

כל רדוקציה נושאת את המקור שממנו נקראה — כותרת בשיעור, תרגיל, או המועדים שבהם נשאלה. רדוקציה שאין לה מקור בקורס מסומנת במפורש כמחוץ לקורפוס.

הכיוון הוא הטענה כולה. $A\le_p B$ אומר ש-$B$ היא הקשה יותר — זו נקודת הכשל הנפוצה ביותר בנושא.

בנייה מודרכת

רשת הרדוקציות של הקורס

שלב 1 מתוך 6
רשת קנונית של רדוקציות בין בעיות NP-שלמותSAT עוברת ל־3SAT, ומשם הרשת מתפצלת לגרפי תאימות, בעיות מסלולים, בעיות חתך וצביעה וקידודים אריתמטיים. כל קשת מציינת את ההמרה הקונקרטית שלה.צייטין + פיצול פסוקיותSAT3SAT
לוגיקה / תאימות
הענף המוצג: מקור לוגי1 המרות מתויגות

28 מתוך 28 רדוקציות

טבלת חישוב וחלונות 2×3המחשה

A ∈ NP ≤p SAT

לכל שפה A∈NPA\in\mathrm{NP} מתקיים A≤pSATA\le_p\mathrm{SAT}. זהו משפט קוק–לוין: SAT\mathrm{SAT} היא NP-קשה, ומכיוון שגם SAT∈NP\mathrm{SAT}\in\mathrm{NP} — היא NP-שלמה.
L9שיעורתרגילבחינה
פונקציית הזהות

3SAT ≤p SAT

3SAT≤pSAT\mathrm{3SAT}\le_p\mathrm{SAT}, ומכאן 3SAT∈NP\mathrm{3SAT}\in\mathrm{NP}.
L8שיעור
פיצול פסוקיות במשתנה עזרהמחשה

SAT ≤p 3SAT

SAT≤p3SAT\mathrm{SAT}\le_p\mathrm{3SAT}, ולכן 3SAT\mathrm{3SAT} היא NP-שלמה.
L8שיעורתרגילבחינה
ריפוד פסוקיות קצרותהמחשה

3SAT ≤p 3SAT=

תהי 3SAT=\mathrm{3SAT}^{=} הבעיה שבה כל פסוקית מכילה בדיוק שלושה ליטרלים. אז 3SAT≤p3SAT=\mathrm{3SAT}\le_p\mathrm{3SAT}^{=}, ולכן גם 3SAT=\mathrm{3SAT}^{=} היא NP-שלמה.
L8שיעור
ליטרל רביעי משותףהמחשה

3SAT ≤p 4NAE

3SAT≤p4NAE\mathrm{3SAT}\le_p\mathrm{4NAE}, ולכן 4NAE\mathrm{4NAE} היא NP-קשה. נוסחה ספיקה במובן NAE אם קיימת השמה שבה בכל פסוקית יש ליטרל שערכו אמת וליטרל שערכו שקר.
L10שיעורבחינה
פיצול NAE במשתנה עזרהמחשה

4NAE ≤p 3NAE

4NAE≤p3NAE\mathrm{4NAE}\le_p\mathrm{3NAE}, ולכן 3NAE\mathrm{3NAE} היא NP-קשה.
L10שיעורבחינה
הגרף המשליםהמחשה

IS ≤p CLIQUE

IS≤pCLIQUE\mathrm{IS}\le_p\mathrm{CLIQUE}: אלגוריתם פולינומי ל-CLIQUE\mathrm{CLIQUE} פותר גם את IS\mathrm{IS}.
L7שיעורתרגיל
הגרף המשלים, בכיוון ההפוךהמחשה

CLIQUE ≤p IS

CLIQUE≤pIS\mathrm{CLIQUE}\le_p\mathrm{IS} — אותה רדוקציה בדיוק, המעבר לגרף המשלים, עובדת גם בכיוון ההפוך.
L7שיעורבחינה
אותו גרף, המשלים של הקבוצההמחשה

IS ≤p VC

IS≤pVC\mathrm{IS}\le_p\mathrm{VC}, ולכן VC\mathrm{VC} היא NP-שלמה.
L10שיעורתרגילבחינה
קודקוד לכל השמה מספקת, קשת לכל סתירההמחשה

3SAT ≤p IS

3SAT≤pIS\mathrm{3SAT}\le_p\mathrm{IS}, ולכן IS\mathrm{IS} היא NP-שלמה.
תרגילבחינה
קשת משתנה, משולש פסוקית, סף $n+2m$המחשה

3NAE ≤p MAXCUT

3NAE≤pMAXCUT\mathrm{3NAE}\le_p\mathrm{MAXCUT} (על מולטיגרפים), ולכן MAXCUT\mathrm{MAXCUT} היא NP-קשה.
L10שיעורתרגילבחינה
קודקוד $N$ ששורף צבע, משולש לכל פסוקיתהמחשה

3NAE ≤p 3COL

3NAE≤p3COL\mathrm{3NAE}\le_p\mathrm{3COL}, ולכן 3COL\mathrm{3COL} היא NP-שלמה.
L10שיעור
קודקוד חדש המחובר להכולהמחשה

3COL ≤p 4COL

3COL≤p4COL\mathrm{3COL}\le_p\mathrm{4COL}, ולכן 4COL\mathrm{4COL} היא NP-שלמה. באופן כללי אותו רעיון נותן 3COL≤pkCOL\mathrm{3COL}\le_p k\mathrm{COL} לכל k≥3k\ge3 קבוע.
L11 · L10שיעור
קודקוד לכל קשת, ואותו $k$המחשה

VC ≤p DS

VC≤pDS\mathrm{VC}\le_p\mathrm{DS}, ולכן DS\mathrm{DS} (קבוצה שולטת) היא NP-שלמה.
L19שיעורבחינה
קליקת פסוקית, קשת ליטרל–שלילה, סף $m$המחשה

SAT ≤p MaxIS

SAT≤pMaxIS\mathrm{SAT}\le_p\mathrm{MaxIS}, ולכן MaxIS\mathrm{MaxIS} היא NP-קשה. כאן MaxIS\mathrm{MaxIS} היא השפה של הזוגות ⟨G,k⟩\langle G,k\rangle שעבורם גודל הקבוצה הבלתי תלויה המקסימלית הוא בדיוק kk.
L22שיעורבחינה
שתילת $k-1$ קודקודים המחוברים לכל הישניםהמחשה

co-IS ≤p MaxIS

IS‾≤pMaxIS\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}, ולכן MaxIS\mathrm{MaxIS} היא coNP-קשה.
L22שיעור
ניפוח כל קשת לגודל 3המחשה

VC ≤p 3H-VC

VC≤p3H-VC\mathrm{VC}\le_p\mathrm{3H\text{-}VC}, ולכן כיסוי קודקודים בהיפרגרף 3-אחיד הוא NP-קשה. היפרגרף 3-אחיד הוא זוג H=(V,E)H=(V,E) שבו כל היפר-קשת היא תת-קבוצה של VV בגודל 33.
L25שיעורתרגיל
חלוקת כל קשת למסלול באורך 3המחשה

Max-Cut-Multi ≤p Max-Cut

Max-Cut-Multi≤pMax-Cut\mathrm{Max\text{-}Cut\text{-}Multi}\le_p\mathrm{Max\text{-}Cut} — הקושי של חתך מקסימלי אינו תלוי בקשתות המקבילות; הוא נשאר גם בגרפים פשוטים.
בחינה
עלה לכל קודקודהמחשה

VC ≤p MODEST

גרף נקרא צנוע אם הדרגה המקסימלית שלו היא לכל היותר 11. הבעיה "האם ניתן להסיר לכל היותר kk קודקודים כך שהגרף הנותר יהיה צנוע" היא NP-שלמה, ברדוקציה VC≤pMODEST\mathrm{VC}\le_p\mathrm{MODEST}.
בחינה
עמודת ספרה לכל קשת, בלי נשאותהמחשה

VC ≤p SUBSET-SUM

VC≤pSUBSET-SUM\mathrm{VC}\le_p\mathrm{SUBSET\text{-}SUM}, ולכן SUBSET-SUM\mathrm{SUBSET\text{-}SUM} היא NP-שלמה.
L11שיעורתרגיל
עמודת משתנה ועמודת פסוקית, עם ספרות ריפודהמחשה

3SAT ≤p SUBSET-SUM

3SAT≤pSUBSET-SUM\mathrm{3SAT}\le_p\mathrm{SUBSET\text{-}SUM} — הגרסה הקלאסית של הרדוקציה, שבה בחירת ההשמה וסיפוק הפסוקיות מקודדים בעמודות ספרות ללא נשאות.
בחינה
איבר ריפוד יחיד, $|2S-T|$המחשה

SUBSET-SUM ≤p PARTITION

SUBSET-SUM≤pPARTITION\mathrm{SUBSET\text{-}SUM}\le_p\mathrm{PARTITION}, ולכן PARTITION\mathrm{PARTITION} היא NP-קשה.
L12שיעורתרגילבחינה
נרמול לפי חצי הסכום, קיבולת $1$, שני תאיםהמחשה

PARTITION ≤p BIN-PACKING

PARTITION≤pBIN-PACKING\mathrm{PARTITION}\le_p\mathrm{BIN\text{-}PACKING}, ולכן BIN-PACKING\mathrm{BIN\text{-}PACKING} היא NP-קשה — ונשארת קשה גם כאשר מספר התאים הוא k=2k=2 קבוע.
L12שיעורתרגילבחינה
שלישיית $v_{in},v_{mid},v_{out}$ לכל קודקודהמחשה

DHC ≤p UHC

DHC≤pUHCDHC\le_p UHC — מעגל המילטוני בגרף מכוון ניתן לרדוקציה למעגל המילטוני בגרף לא מכוון, על ידי קידוד הכיווניות בתוך מבנה הגרף.
בחינה
מעגל של ארבע רדוקציות במקום 12המחשה

DHP/DHC/UHC/UHP ≤p each other

בין כל שתיים מארבע הבעיות DHPDHP, DHCDHC, UHPUHP, UHCUHC קיימת רדוקציה בזמן פולינומי; כלומר כולן שקולות פולינומית, ולכן כולן NP-קשות.
L12 · L12שיעורבחינה
השלמה לגרף מלא, משקלים $1$ ו-$2$, תקציב $|V|$המחשה

UHC ≤p TSP

UHC≤pTSPUHC\le_p TSP, ולכן TSPTSP היא NP-קשה (ועם השייכות ל-NP — NP-שלמה).
L12שיעורתרגילבחינה
משקל ענק $\alpha|V|+1$ לקשת חסרהחסם אי-קירובהמחשה

UHC ≤p TSP-OPT

לכל α≥1\alpha\ge1: אם קיים אלגוריתם קירוב ביחס α\alpha לגרסת האופטימיזציה של TSPTSP הכללי, אז P=NP\mathrm{P}=\mathrm{NP}. למעשה מתקיימת שקילות: קיום קירוב כלשהו   ⟺  P=NP\iff \mathrm{P}=\mathrm{NP}.
L13שיעורתרגיל
פער בין $\mathrm{OPT}=2$ ל-$\mathrm{OPT}=3$חסם אי-קירובהמחשה

PARTITION ≤p BIN-PACKING-OPT

אם קיים אלגוריתם פולינומי לבעיית האריזה למכלים ביחס קירוב מוחלט הקטן מ-32\tfrac32 — ובפרט ביחס 1.491.49 — אז P=NP\mathrm{P}=\mathrm{NP}.
L25 · L12שיעורתרגיל