מפת הסיבוכיות
EN
גלריה אינטראקטיבית

גלריית המחשות

42 המחשות אינטראקטיביות מהשיעורים ומהתרגילים, מרוכזות במקום אחד.

יסודות ומודלים חישוביים

4 המחשות

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

בנייה מודרכת

מפת קצבי גידול

שלב 1 מתוך 6
השוואת קצבי גידולעקומות עבור log n, n, n log n, n בריבוע ושתיים בחזקת n בסקאלה אנכית ליניארית.01,0242,0483,0724,09624681012גודל הקלט nערך הפונקציה (סקאלה ליניארית)log₂ n
log₂ n
להמשך הלמידה

עקבו אחר מכונה דטרמיניסטית לאורך קונפיגורציות תוך מעקב אחר צריכת המקום.

בנייה מודרכת

גרף קונפיגורציות דטרמיניסטי

שלב 1 מתוך 7
קלט x=1010שמורה: המצב מתעד את זוגיות סימני ה־1 שכבר נסרקוδ(q_even, 1) = (q_odd, R)
מסלול הקונפיגורציות של מכונת זוגיות דטרמיניסטיתשש קונפיגורציות יוצרות מסלול יחיד. לכל קונפיגורציה שאינה עוצרת יש מעבר יוצא אחד בדיוק.q_evenראש = 0קורא 1[1] 0 1 0 □
q_evenמיקום הראש 0 · הסמל הנקרא 1
1
0
1
0
□
המעבר הבא היחידδ(q_even, 1) = (q_odd, R)
קונפיגורציה שביקרנו בהמעבר חוקי יחידמיקום הראש הנוכחי
להמשך הלמידה

עקבו אחר רצף בחירות מקבל בעץ חישוב מתפצל וקראו אותו כתעודה.

בנייה מודרכת

עץ חישוב אי־דטרמיניסטי

שלב 1 מתוך 7
φ =(x₁ ∨ ¬x₂)∧(x₂ ∨ x₃)
עץ חישוב לא־דטרמיניסטי בינאריהמאמת מנחש שלוש סיביות השמה. שמונה עלים בודקים את הנוסחה, והמסלול 110 מגיע לעלה מקבל.ε
בחירה בינארית חוקית
להמשך הלמידה
לתרגול

מקמו את P,‏ NP ו־coNP בעזרת ההכלות הידועות בלבד, תוך סימון מפורש של שוויונות פתוחים.

בנייה מודרכת

NP ו־coNP

שלב 1 מתוך 6
ידוע: P⊆NP
הכלות ידועות בין P, NP ו־coNPגבולות סכמטיים ומקווקווים של NP ו־coNP חופפים. P מוכלת בחיתוך שלהם. SAT ו־UNSAT מדגימות שיוכי תעודות ידועים, ואילו P מול NP ו־NP מול coNP נשארות שאלות פתוחות.NPתעודות כן קצרות
גבול סכמטי של מחלקה
להמשך הלמידה

רדוקציות וקידודים

24 המחשות

בנו גאדג׳טים לפסוקיות, הוסיפו קשתות סתירה, בחרו את הסף והוכיחו את שני הכיוונים.

בנייה מודרכת

3SAT → קבוצה בלתי תלויה

שלב 1 מתוך 7
φ =(x ∨ y ∨ z)∧(¬x ∨ y ∨ w)∧(¬y ∨ z ∨ w)
בנייה מ־3SAT לקבוצה בלתי תלויהשלוש פסוקיות הופכות לגאדג׳טים משולשים. קשתות רציפות מחברות ליטרלים באותה פסוקית, קשתות מקווקוות מחברות ליטרלים משלימים, ובשלב האחרון נבחרים x, y ו־z כקבוצה בלתי תלויה בגודל שלוש.C1x ∨ y ∨ zפסוקית מקורC2¬x ∨ y ∨ wפסוקית מקורC3¬y ∨ z ∨ wפסוקית מקור
קשת באותה פסוקיתסתירה בין משלימים
להמשך הלמידה
לתרגול

הפכו כל אי־קשת לקשת, השאירו את אותה קבוצת קודקודים ואת אותו סף, וקראו קבוצה בלתי־תלויה כקליקה.

בנייה מודרכת

קבוצה בלתי תלויה → קליקה

שלב 1 מתוך 6
קבוצה בלתי־תלויה לקליקה דרך משלים גרףמסלול על ארבעה קודקודים מושלם; זוג בלתי־תלוי הופך לקליקה בעוד שהסף נשאר k.מקור G1234משלים Ḡ1234
קשת מקור (נמחקת)קשת משלים (נוספת)
להמשך הלמידה
לתרגול

השאירו את אותו גרף, השלימו את קבוצת הקודקודים הנבחרת, והעבירו את הסף k אל |V|−k.

בנייה מודרכת

קבוצה בלתי תלויה → כיסוי קודקודים

שלב 1 מתוך 6
קבוצה בלתי־תלויה לכיסוי קודקודים דרך משלים קבוצהקבוצה בלתי־תלויה במסלול מושלמת לכיסוי קודקודים בעוד שהסף הופך ל־n פחות k.אותו גרף G1234
להמשך הלמידה
לתרגול

פצלו פסוקית CNF ארוכה לשרשרת שלשות שוות־ספיקות עם משתנים חדשים, בלי דיסטריבוטיביות אקספוננציאלית.

בנייה מודרכת

SAT → 3SAT

שלב 1 מתוך 6
פסוקית מקור(a ∨ b ∨ c ∨ d ∨ e)
SAT ל־3SAT בפיצול פסוקיותפסוקית בת חמישה ליטרלים מוחלפת בשלוש שלשות חופפות הקשורות בשני משתנים חדשים.פסוקית מקור
משתנה טרישלשת פלט
להמשך הלמידה
לתרגול

מקמו קודקודי ליטרלים, חתכו כל זוג משתנים, ניקדו שתי קשתות לכל משולש פסוקית, והגיעו לסף n+2m.

בנייה מודרכת

NAE-3SAT → Max-Cut

שלב 1 מתוך 7
NAE-3CNF מקור(x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)
NAE-3SAT ל־Max-Cut במולטי־גרףקודקודי ליטרלים עם קשתות משתנים ומשולשי פסוקיות; חתך בגודל n+2m מקודד השמת NAE.NAE-3CNF מקור
קשת משתנהקשת פסוקית
להמשך הלמידה
לתרגול

השלימו את הגרף, תמחרו קשתות מקוריות ב־1 וקשתות חסרות ב־2, קבעו תקציב B = n, וקראו מסע זול בחזרה כמעגל המילטוני.

בנייה מודרכת

מעגל המילטוני → TSP

שלב 1 מתוך 6
מעגל המילטוני ל־TSP על חמישה קודקודיםמחומש של חמש קשתות מקוריות בעלות 1 מושלם על ידי כוכב מחומש של חמישה אלכסונים בעלות 2; המחומש עצמו הוא מסע בעלות חמש, בדיוק גובה התקציב B = n = 5.גרף המקור G — 5 קודקודים, 5 קשתות12345
קשת מקורית של G — עלות 1
להמשך הלמידה
לתרגול

הוסיפו את הסמנים S+T ו־2S−T כך שחלוקה שווה של הסכום החדש 4S חייבת להפריד ביניהם ולחשוף תת־קבוצה שסכומה T.

בנייה מודרכת

סכום תת־קבוצה → חלוקה

שלב 1 מתוך 6
A = {3, 5, 6, 11}T = 14
מסכום תת־קבוצה לחלוקה באמצעות שני סמנים שנוספיםעמודות פרופורציוניות ל־3, 5, 6, 11 ולסמנים 39 ו־36 ממלאות שתי כפות שסכום כל אחת מהן 50.המספרים משורטטים לפי גודלם35611
מספר מקורי
להמשך הלמידה
לתרגול

בדקו את כיוון הרדוקציה ועקבו אחר העברת הקושי בשרשרת בעיות קנוניות.

בנייה מודרכת

שרשרת רדוקציות לבעיות NP-שלמות

שלב 1 מתוך 5
הבעיה הקשה הידועה Aמופע המקור x
f(x)מהדר פולינומי כולל
פותר לבעיית היעד Bאלגוריתם מהיר היפותטי
תשובת כן/לא של הפותר מכריעה את A
להמשך הלמידה
לתרגול

חקרו את רשת הרדוקציות של הקורס ואת ההעתקה שמבצעת כל קשת.

בנייה מודרכת

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

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

העמודים שמהם זה נכתב

1 עמודים

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

להמשך הלמידה

המירו חישוב חסום לאילוצים בוליאניים בעזרת חלונות מקומיים בטבלה.

בנייה מודרכת

טבלת קוק–לוין

שלב 1 מתוך 7
קלט x = 10 · חסם זמן T = 3 · רוחב הטבלה S = 5
t=0
⊢
[q0,1]
0
□
□
להמשך הלמידה
לתרגול

קדדו בחירות אמת וסיפוק פסוקיות בעמודות ספרות ללא נשא.

בנייה מודרכת

3SAT → Subset Sum

שלב 1 מתוך 6
φ = (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂)
מספר
x₁
x₂
C₁
C₂

העמודים שמהם זה נכתב

2 עמודים

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

להמשך הלמידה

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

3NAE → צביעה ב-3 צבעים

שלב 1 מתוך 7
הקלט φ(x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)
מ-3NAE לצביעה ב-3 צבעים: N, קודקודי ליטרלים ומשולשי פסוקיותקודקוד מיוחד N מחובר בקשתות שחורות לשישה קודקודי ליטרלים; קשתות כחולות מחברות כל ליטרל לשלילתו; לכל אחת משתי הפסוקיות משולש אדום משלה שקודקודיו מחוברים לליטרלים של אותה פסוקית.NN — שורף את צבע 1x¬xy¬yz¬zקודקודי ליטרלים — 2n = 61:x1:y1:z2:¬x2:y2:¬zC₁ = (x ∨ y ∨ z)C₂ = (¬x ∨ y ∨ ¬z)קודקודי פסוקית — 3m = 6

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

צביעה ב-3 → צביעה ב-4

שלב 1 מתוך 7
מצביעה ב-3 לצביעה ב-4: הוספת קודקוד אחד המחובר להכולבפאנל השמאלי גרף הקלט עם צביעה; בפאנל הימני אותו גרף בתוספת קודקוד חדש המחובר לכל קודקוד מקורי, עם הצביעה שלו. בצעדים המאוחרים הקלט מוחלף ב-K₄ ומושווים פונקציית הזהות, קודקוד מבודד נוסף, והבנייה האמיתית.מופע קלט של 3COLG = C₅v₁1v₂2v₃1v₄2v₅3C₅ ∈ 3COL ✓
קשת של G (נשמרת)צבע 1 (מקווקו)צבע 2 (רציף)צבע 3 (מנוקד)

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

כיסוי קודקודים → קבוצה שולטת

שלב 1 מתוך 7
⟨G, k = 2⟩ ∈ VC ?
כיסוי קודקודים לקבוצה שולטת: קודקוד לכל קשת, ומחיקת קודקודים מבודדיםגרף המקור G עם הקודקודים a, b, c, d וקודקוד מבודד z מופיע בצד אחד. בצד השני הגרף Ĝ מוסיף קודקוד לכל קשת ומחבר אותו לשני קצותיה, מוחק את z, ושומר את אותו סף k. ההדגשות מראות את הכיסוי U שמשמש כקבוצה שולטת, קבוצה שולטת שמכילה קודקוד חדש, ואת מפת התיקון שמחזירה את הקודקוד החדש לקודקוד מקורי.G — גרף המקורabcdzמבודד
קודקוד מקורי מתוך V

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

כיסוי קודקודים → סכום תת-קבוצה

שלב 1 מתוך 8
G = P₅: |V| = 5, m = |E| = 4K = 3
מסלול הקלט לצד תרשים של סכומי עמודות הקשתותמשמאל מסלול בן חמישה קודקודים וארבע קשתות, כשעל כל קשת תג המציין כמה מקצותיה נבחרו. מימין עמודה אחת לכל עמודת קשת, מפוצלת לחלק שתרמו הקודקודים הנבחרים ולחלק שתרם מספר הקשת עצמה, על רקע קווי עזר ביעד 2, במקסימום 3 ובסף הנשאות 10.G — גרף הקלטסכומי עמודות הקשתות cⱼe₁e₂e₃e₄v₁v₂v₃v₄v₅02310e₁e₂e₃e₄
מספר קודקוד a_v
שורה לכל מספר שנבנה; עמודה אחת ל־d ועמודה לכל קשת; השורות האחרונות הן סכומי העמודות וסכום היעד.
מספרde₁e₂e₃e₄ערך
צעד 0 — "לכל היותר K" הופך ל"בדיוק K"אם K > |V| מחליפים את K ב־|V|. כיסוי בגודל ≤ K תמיד אפשר להשלים לגודל K בדיוק, ולכן כפיית K בעמודה d אינה מזיקה.

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

SAT → MaxIS

שלב 1 מתוך 7
φ = (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂ ∨ x₃) ∧ (¬x₂ ∨ ¬x₃)m = 3 פסוקיות
הגרף G_φ הנבנה מנוסחת CNF בת שלוש פסוקיותשבעה קודקודים מסודרים בשלושה טורי פסוקיות. קשתות אדומות מלאות הופכות כל פסוקית לקליקה; קשתות כהות מקווקוות מחברות כל ליטרל לשלילתו. שלושה קודקודים נבחרים, אחד מכל פסוקית, מרכיבים קבוצה בלתי תלויה בגודל שלוש.G_φ — קודקוד לכל מופע ליטרלC₁ = (x₁ ∨ ¬x₂)C₂ = (¬x₁ ∨ x₂ ∨ x₃)C₃ = (¬x₂ ∨ ¬x₃)x₁¬x₂¬x₁x₂x₃¬x₂¬x₃¬x₂ מופיע פעמיים ← שני קודקודים
קודקוד = מופע ליטרל אחד

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

משלים IS → MaxIS

שלב 1 מתוך 7
⟨G, k⟩ = ⟨C₅, 4⟩משלים IS: האם אין ב־G קבוצה בלתי תלויה בגודל 4?
למת המשלימיםf רדוקציה מ־A ל־B ⇔ f רדוקציה מ־Ā ל־B̄ — ולכן מותר לצאת ממשלים IS.
מעגל באורך חמש ושלושה קודקודים שתולים המחוברים לכל קודקוד מקוריגרף המקור הוא מחומש בן חמישה קודקודים. שלושה קודקודים שתולים ניצבים בטור מימינו, בלי קשתות ביניהם ועם קשת דקה אל כל אחד מחמשת הקודקודים המקוריים. בשלב ההשוואה מוצג אותו גרף פעמיים, פעם עם קשתות החיבור ופעם בלעדיהן.G = C₅ — גרף הקלטv₁v₂v₃v₄v₅α(G) = 2 ≤ k − 1 = 3, אך לא בהכרח שווה
קודקוד מקורי של Vמלא: קשת מקורית של Gהקבוצה הבלתי תלויה הנדונה, מוקפת ב־✓

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

כיסוי קודקודים → כיסוי בהיפרגרף 3-אחיד

שלב 1 מתוך 7
⟨G, k = 2⟩ ∈ VC ?
כיסוי קודקודים לכיסוי בהיפרגרף 3-אחיד: כל קשת מנופחת בעזרת קודקוד חדשגרף המקור G עם הקודקודים a, b, c, d והקשתות ab, ac, bc, cd מופיע בצד אחד. בצד השני ההיפרגרף H שומר את ארבעת הקודקודים, מוסיף קודקוד ריבועי לכל קשת, ומצייר כל היפר־קשת כשטח מוצלל שמכסה בדיוק שלושה קודקודים. ההדגשות מראות את הכיסוי U שנשאר ללא שינוי, כיסוי של ההיפרגרף שמכיל קודקוד חדש, ואת מפת התיקון שמחליפה אותו באחד משני קצותיו האמיתיים.G — גרף המקור (קשתות בגודל 2)abacbccdabcd
קודקוד מקורי מתוך V (עיגול)

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

Max-Cut במולטיגרף → בגרף פשוט

שלב 1 מתוך 7
|E| = 4k = 3
Max-Cut במולטיגרף ברדוקציה ל‑Max-Cut בגרף פשוטמשמאל מולטיגרף עם שתי קשתות מקבילות ולולאה; מימין הגרף הפשוט שבו כל קשת הפכה למסלול באורך שלוש דרך שני קודקודים ייחודיים, עם סימון צדי החתך, הקשתות החוצות ומקרי הזוגיות.G — מולטיגרףe₁e₂e₃e₄abcG′ — גרף פשוטV′ = V ∪ V″ — נבנה בשלב הבא
קודקוד מקורי מ‑V

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

כיסוי קודקודים → גרף צנוע

שלב 1 מתוך 7
⟨G, k = 3⟩ ∈ VC ?צנוע ⇔ כל דרגה ≤ 1
כיסוי קודקודים לגרף צנוע: עלה תלוי על כל קודקוד מקוריגרף המקור G, משולש a, b, c עם קודקוד תלוי d היוצא מ־c, מופיע בצד אחד. בצד השני הגרף G′ תולה עלה קטן על כל אחד מ־a, b, c ו־d. ליד כל קודקוד ששורד מופיע תג דרגה, קודקודים שנמחקו מסומנים בקו חוצה, וההדגשות מראות את הכיסוי U המשמש כקבוצת הסרה, קבוצת הסרה שמבזבזת יחידה על עלה, ואת מפת התיקון שמחליפה את העלה בקודקוד שהוא תלוי בו.G — גרף המקורabcd
קודקוד מקורי מתוך V (עיגול גדול)קשת מקורית מתוך E

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

מעגל המילטוני מכוון → לא מכוון

שלב 1 מתוך 7
מעגל המילטוני מכוון ברדוקציה למעגל המילטוני לא מכווןמשמאל גרף מכוון על ארבעה קודקודים; מימין כל קודקוד מורחב לשלישייה in, mid, out המסודרת סביב מעגל, כך שהמעגל ההמילטוני עובר על הטבעת וקודקודי האמצע מדרגה שתיים כופים כיוון אחיד.G — מכוון1→22→33→44→13→11234G′ — לא מכווןכל קודקוד עומד להפוך לשלישייה

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

3SAT → 4NAE

שלב 1 מתוך 7
φ = (x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ ¬x₃) ∧ (x₁ ∨ ¬x₂ ∨ ¬x₃)
מ-3SAT ל-4NAE: טבלת פסוקיות עם הליטרל z שנוסףכל שורה היא פסוקית וכל תא הוא ליטרל, צבוע לפי ערכו תחת ההשמה הנוכחית. העמודה הרביעית מחזיקה את הליטרל החדש המשותף z. תוויות ההכרעה מימין אומרות אם הפסוקית מסופקת ואם היא מסופקת במובן NAE.φ תחת v = (1,1,1) — מסופקת, אבל פסוקית 1 כולה אמתC₁x₁ = 1x₂ = 1x₃ = 1מסופקת ✓כולם שווים ✗C₂¬x₁ = 0x₂ = 1¬x₃ = 0מסופקת ✓NAE ✓C₃x₁ = 1¬x₂ = 0¬x₃ = 0מסופקת ✓NAE ✓x₁ = 1x₂ = 1x₃ = 1
ערך הליטרל 1ערך הליטרל 0

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

4NAE → 3NAE

שלב 1 מתוך 7
4NAE ברדוקציה ל‑3NAE על ידי פיצול כל פסוקיתשתי פסוקיות בנות ארבעה ליטרלים מפוצלות כל אחת לשתי פסוקיות בנות שלושה ליטרלים המחוברות במשתנה עזר ובשלילתו; ערכי הליטרלים מסומנים בעיגול עבור אמת ובריבוע עבור שקר, ואחריהם שלושת מקרי הכיוון הראשון וחילוץ ליטרל אמת וליטרל שקר בכיוון ההפוך.φ — 4CNF, בקריאת NAEC₁xℓ₁yℓ₂zℓ₃¬wℓ₄C₂¬xℓ₁wℓ₂zℓ₃yℓ₄כל פסוקית עומדת להתפצל לשתייםכל פסוקית עומדת להתפצל לשתיים

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

3SAT → בדיוק-3SAT

שלב 1 מתוך 7
v: x₁ = F, x₂ = F, x₃ = T
ריפוד פסוקיות קצרות עד בדיוק שלושה ליטרליםשלוש פסוקיות הקלט, באורכים שלוש, שתיים ואחת, ממופות לשבע פסוקיות פלט: הפסוקית המלאה מועתקת, הפסוקית בת שני הליטרלים הופכת לשתי פסוקיות עם משתנה עזר אחד, והפסוקית היחידה הופכת לארבע פסוקיות עם שני משתני עזר.φ — קלט, לכל היותר 3 ליטרליםf(φ) — פלט, בדיוק 3 ליטרליםנבנית פסוקית אחר פסוקית|C₁| = 3 · משאיריםC₁x₁∨¬x₂∨x₃|C₂| = 2 · מרפדים ב־y₂C₂¬x₁∨x₂|C₃| = 1 · מרפדים ב־y₃, y₃′C₃x₃
ליטרל של φ

מחלקות סיבוכיות ומקום

6 המחשות

הבחינו בין הכלות והפרדות מוכחות לבין שוויונות פתוחים בין מחלקות.

בנייה מודרכת

הכלות בין מחלקות סיבוכיות

שלב 1 מתוך 4
Pזמן פולינומי דטרמיניסטי
הכלה מוכחת
להמשך הלמידה

בנו את רמות הכמתים של PH ובחנו את משפט הקריסה המותנה.

בנייה מודרכת

סריג ההיררכיה הפולינומית

שלב 1 מתוך 6
Σ₀ᴾ = Π₀ᴾ = Pפרדיקט בזמן פולינומי
מתחילה בכמת קיומימתחילה בכמת אוניברסלי
להמשך הלמידה
לתרגול

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

בנייה מודרכת

רקורסיית סביץ׳

שלב 1 מתוך 6
גרף הקונפיגורציות והרקורסיה של סביץ׳הגרף 1 אל 2 אל 3, עם קשת נוספת מ־1 אל 4, מתואם עם רקורסיית עומק תחילה עבור REACH בין 1 ל־3 ברמה 2.גרף קונפיגורציות מרומז1234מסלול עד: 1 → 2 → 3 (2 ≤ 4)רקורסיית עומק תחילההקריאה החסומה תופיע בשלב הבא
מסלול עדמסגרת מחסנית פעילה
להמשך הלמידה
לתרגול

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

בנייה מודרכת

טיעון ריפוד

שלב 1 מתוך 6
המקור xx = 101
101
n = |x| = 3
המופע המשמעותי xסיומת הריפוד
להמשך הלמידה
לתרגול

הפעילו סימולציה אוניברסלית עם שעון, הפכו את התשובה על האלכסון, והפרידו בין DTIME(n²) ל־DTIME(n³) דרך תקורת ה־t·log t.

בנייה מודרכת

אלכסון במשפט היררכיית הזמן

שלב 1 מתוך 6
החסם המדומה t₁(n) = n²חסם מכונת האלכסון t₂(n) = n³
הריפוד גורם לכל מכונה לחזור

לאותה מכונה יש קלטים ארוכים כרצוננו, ולכן בסופו של דבר יש לשעון מקום

⟨M₃⟩10⁰⟨M₃⟩10¹⟨M₃⟩10²⟨M₃⟩10³…
טבלת האלכסון של משפט היררכיית הזמןשורות M₁ עד M₅ מול הקלטים המרופדים העצמיים w₁ עד w₅, תקציב שעון של n² צעדים בכל עמודה, תאי האלכסון מתהפכים לשורת D, וסימן אי־התאמה מתחת לכל עמודה.מכונה ╲ קלטw₁⟨M₁⟩10ᵏw₂⟨M₂⟩10ᵏw₃⟨M₃⟩10ᵏw₄⟨M₄⟩10ᵏw₅⟨M₅⟩10ᵏM₁·טרם הורצה·טרם הורצה·טרם הורצה·טרם הורצה·טרם הורצהM₂·טרם הורצה·טרם הורצה·טרם הורצה·טרם הורצה·טרם הורצהM₃·טרם הורצה·טרם הורצה·טרם הורצה·טרם הורצה·טרם הורצהM₄·טרם הורצה·טרם הורצה·טרם הורצה·טרם הורצה·טרם הורצהM₅·טרם הורצה·טרם הורצה·טרם הורצה·טרם הורצה·טרם הורצה
טרם הורצה

העמודים שמהם זה נכתב

2 עמודים

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

להמשך הלמידה
לתרגול

תנו לכל המכונות את אותו אורקל, השוו בין העולם שבו P^A = NP^A לעולם שבו P^B ≠ NP^B, וראו מה הוכחה שעוברת לכל אורקל לעולם לא תוכל להכריע.

בנייה מודרכת

מחסום הרלטיביזציה

שלב 1 מתוך 6
שני עולמות אורקל החולקים מכונה אחתמכונת אורקל אחת מזינה את אותה שרשרת הכלות P^O ⊆ NP^O ⊆ PSPACE^O לעולם A, שבו המחלקות שוות, ולעולם B, שבו הן מופרדות.מכונת אורקל — אותה מכונה בשני העולמותMסרט עבודהכתיבת qסרט שאילתותצעד אחדאורקל Oq ∈ Oq ∉ Oכתיבת q עולה זמן, ולכן השאילתות נשארות באורך פולינומי.
מבנה משותף — נכון לכל אורקל

העמודים שמהם זה נכתב

2 עמודים

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

להמשך הלמידה
לתרגול

אלגוריתמים וקירוב

8 המחשות

מלאו טבלת תכנות דינמי פסאודו־פולינומית ושחזרו ממנה פתרון.

בנייה מודרכת

תכנות דינמי ל־Subset Sum

שלב 1 מתוך 6
A = {3, 5, 6, 11} · יעד T = 14
i / סכום
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0 פריטים
✓
·
·
·
·
·
·
·
·
·
·
·
·
·
·
להמשך הלמידה
לתרגול

כווצו קשתות אקראיות, שמרו קשתות מקבילות וחשפו את החתך הסופי.

בנייה מודרכת

כיווץ קרגר

שלב 1 מתוך 6
כיווץ קרגר על ריבוע עם אלכסון אחדחתך מינימלי מוגן בן שתי קשתות בקודקוד B שורד את כיווץ האלכסון A C ולאחריו קשת בטוחה אל D. קשתות מקבילות נשמרות ולולאה עצמית נמחקת.ABCDהחתך המוגן F בקודקוד B, λ=2
חתך קבוע המשמש רק לניתוחקשת בטוחה שמכווצים
להמשך הלמידה
לתרגול

הריצו אלגוריתם RP שוב ושוב וקחו OR, הריצו אלגוריתם BPP וקחו הכרעת רוב, וראו כיצד השגיאה דועכת אקספוננציאלית במספר הריצות הבלתי תלויות.

בנייה מודרכת

הגברת ההצלחה של אלגוריתמים אקראיים

שלב 1 מתוך 6
הגברת שגיאה באלגוריתמים אקראיים על פני הרצות בלתי תלויותרצועת הרצות בלתי תלויות מזינה שער OR עבור RP ושער רוב עבור BPP, ומעליהם גרף בסקאלה לוגריתמית המשווה את שגיאת RP שהיא שתיים בחזקת מינוס k, את שגיאת הרוב המדויקת של BPP, את תקרת הופדינג e בחזקת מינוס k חלקי שמונה־עשרה, וקו ישר המתאר שימוש חוזר באותה מחרוזת אקראית.הרצות בלתי תלויות (המחשה קבועה)RP · OR✗BPP · רוב✓הסתברות השגיאה כפונקציה של מספר ההרצות110⁻¹10⁻²10⁻³10⁻⁴10⁻⁵10⁻⁶10⁻⁷159131721k הרצות בלתי תלויותהסתברות שגיאה (סקאלה לוגריתמית)
✓ ההרצה מקבלת מופע כן · ההרצה עונה נכון✗ ההרצה מפספסת מופע כן · ההרצה עונה שגוי
הרצה אחת מכל סוגRP: Pr[accept | yes] ≥ 1/2, Pr[accept | no] = 0BPP: Pr[correct] ≥ 2/3 על כל קלטכל תוצאה מוצגת היא המחשה קבועה, ולכן התמונה זהה אצל כל הקוראים.

העמודים שמהם זה נכתב

3 עמודים

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

להמשך הלמידה
לתרגול

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

בנייה מודרכת

קירוב 2 ל־TSP מטרי בשיטת העץ הכפול

שלב 1 מתוך 6
קירוב 2 ל־TSP מטרי בשיטת העץ הכפול על חמש נקודותמופע מטרי מלא על חמש נקודות הופך לעץ פורש מינימלי, אחר כך לרב־גרף כפול, אחר כך למעגל אוילר, ולבסוף למסע המילטוני מקוצר.מופע מטרי מלא8151319871210117ABCDE
קשת מטרית עם עלותה
אי־שוויון המשולשעלויות: AB 8, AC 15, AD 13, AE 19, BC 8, BD 7, BE 12, CD 10, CE 11, DE 7מתקיים בכל שישים השלשות הסדורות של נקודות שונות

העמודים שמהם זה נכתב

1 עמודים

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

להמשך הלמידה
לתרגול

הפכו מופע חלוקה לפחים בקיבולת S/2, ראו כיצד האופטימום מצטמצם ל־2 או ל־3, והסיקו שאף אלגוריתם פולינומי אינו משיג יחס מוחלט טוב מ־3/2 אלא אם P = NP.

בנייה מודרכת

חלוקה → אריזת פחים ומחסום ה־3/2

שלב 1 מתוך 6
A′ = {3, 5, 6, 11, 39, 36}S = 100
חלוקה הממופה לפחים בקיבולת S/2 יחד עם סרגל יחס ה־3/2מלבני פריטים המשורטטים לפי גודלם ממלאים פחים בקיבולת 50 עד קו הקיבולת במופע הפתיר, ומשאירים שארית מוצללת בשלושה פחים בקיבולת 51 במופע שאינו פתיר, לצד סרגל יחסים המסומן ב־1, 11/9, 3/2, 1.7 ו־2.הפריטים משורטטים לפי גודלם356113936
מלבן פריט, גובהו פרופורציוני לערכו

העמודים שמהם זה נכתב

3 עמודים

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

להמשך הלמידה
לתרגול

עקבו אחר חסמים בכיוון הנכון עבור אלגוריתמי מינימיזציה ומקסימיזציה.

בנייה מודרכת

גשרי הוכחה ליחס קירוב

שלב 1 מתוך 6
מינימיזציהOPT ≤ A ≤ α·OPTחוסמים מלמעלה את תוצאת האלגוריתם בעזרת חסם תחתון על OPT.
מקסימיזציהOPT/α ≤ A ≤ OPTחוסמים מלמטה את תוצאת האלגוריתם בעזרת חסם עליון על OPT.
חסם תחתון למינימיזציהחסם עליון למקסימיזציה
להמשך הלמידה

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

ל-TSP הכללי אין קירוב קבוע

שלב 1 מתוך 7
n = |V| = 5 · α = 2 · α|V|+1 = 11 · סף αn = 10
שני גרפים בני חמישה קודקודים שהושלמו במשקלים ענקיים, והפער בין שני האופטימומים האפשרייםמשמאל גרף המילטוני שהמסלול האופטימלי בו עולה חמש; מימין עניבת פרפר שאינה המילטונית, שבה המסלול הזול ביותר נאלץ לקנות קשת במשקל אחת עשרה ולעלות חמש עשרה. ציר משותף מציג את קטע הכן מחמש עד עשר, את סף הקבלה בעשר, ואת קטע הלא מחמש עשרה ומעלה, עם רצועה ריקה ביניהם.G ∈ UHCעניבת פרפר + המיתר {2,4}12345G ∉ UHCעניבת פרפר: 3 הוא קודקוד חתך12345
קשת מקורית, w = 1
מדוע קיים מעגל המילטוניהמיתר {2,4} סוגר את המעגל 1→2→4→5→3→1, העובר בכל קודקוד בדיוק פעם אחת ומשתמש רק בקשתות של G.
מדוע אין מעגל כזה בעניבת הפרפרמחיקת קודקוד 3 מותירה את שני הרכיבים {1,2} ו־{4,5}. מעגל המילטוני היה נאלץ לעבור בקודקוד 3 פעמיים כדי לבקר בשניהם, ומעגל אינו יכול לעשות זאת.

עקבו אחר הבנייה ואחר שני כיווני ההוכחה.

בנייה מודרכת

אריזה למכלים: מחסום היחס המוחלט 3/2

שלב 1 מתוך 7
bᵢ = 2aᵢ/S · Σbᵢ = 2 · bᵢ ∈ (0,1] · קיבולת 1
שני מופעי אריזה מנורמלים שסכומם שתיים, והציר השלם שעליו האופטימום הוא שתיים או שלושמשמאל מופע כן שששת פריטיו מתחלקים לשני תאים המלאים בדיוק עד קיבולת אחת; מימין מופע לא הזקוק לשלושה תאים עם שארית גלויה. מתחת, ציר המסומן רק במספרים שלמים מציג את האופטימום בשתיים או בשלוש, את הרצועה הריקה ביניהם, ואת הערך 2ρ השווה ל־2.98 המתמוטט אל 2.פריטים מנורמלים, bᵢ = 2aᵢ/S, סכום 20.060.100.120.220.780.72A ∈ PARTITIONA = {3, 5, 6, 11, 39, 36}, S = 100קיבולת = 10.060.080.120.240.780.72A″ ∉ PARTITIONA″ = {3, 4, 6, 12, 39, 36}, S = 100קיבולת = 1
פריט מנורמל bᵢקיבולת תא 1