שיעורים
142 עמודי סיכום בכתב יד, לצד 30 קובצי תמלול.
סמסטר ב׳ 2026 — השיעורים במלואם
עשרים ושישה שיעורים שנבנו מחדש משני מקורות: סיכומי הכתב יד של גיא סופר, ותמלולי ההקלטות של השיעורים עצמם. כל שיעור מביא את ההוכחות במלואן, את הדוגמאות שנפתרו בכיתה ואת ההערות שנאמרו בעל פה ואינן בסיכום.
בביטחון גבוה
3 בינוני, 1 נמוך. הדירוג משקף כמה מקורות מאשרים כל שיעור.
ללא הקלטה
שיעורים 8, 14, 23 נכתבו מן הסיכום בלבד — אין להם הקלטה בשום מקום בקורפוס, וכל אחד מהם אומר זאת במפורש.
מה יש בכל קובץ
מבנה קבוע: בקצרה · רקע ותלויות · הגדרות · משפטים והוכחות · דוגמאות ותרגילים · הערות מהשיעור · פערים בין הסיכום להקלטה · נקודות למבחן. המקטע על הפערים אינו הערת שוליים אלא תוצר עיקרי — הוא מתעד טעויות מתמטיות שתוקנו במקור, קטעים בלתי קריאים ששוחזרו, וחומר שקיים רק באחד המקורות.
הקבצים הם טיוטה ולא עברו בדיקה אנושית. התיקונים שבהם הם שיפוט מתמטי מול כתב יד ומול תמלול אוטומטי — מנומקים ומתועדים, אך לא מאומתים.
השיעורים
- 1ממה ניתן לחשב למה ניתן לחשב ביעילות: המודל, המשאבים והמחלקות הבסיסיותהשיעור מעביר את השאלה המרכזית מ'מה ניתן לחשב' ל'מה ניתן לחשב ביעילות', מקבע את מכונת הטיורינג כסרגל המדידה, מגדיר את משאבי הזמן והמקום, מנתח את מחיר הסימולציות (רב-סרטית והמכונה האוניברסלית), ומוכיח את הקשרים הדו-כיווניים בין זמן למקום ואת ההכלות בין $DTime$ ל-$DSpace$.
- 2חישוב יעיל: מחלקות הזמן והמקום DTime ו-DSpaceבשיעור הזה מוגדרות מחלקות הסיבוכיות הבסיסיות $\mathrm{DTime}(f)$ ו-$\mathrm{DSpace}(f)$, נגזרים מהן ההכלות הבסיסיות בין זמן למקום, ומוגדרות המחלקות הגסות P, EXP, PSPACE ו-EXPSPACE.
- 3משפטי היררכיה במקום ובזמןיותר משאב נותן ממש יותר כוח: הוכחת משפט ההיררכיה במקום בלכסון על מכונה אוניברסלית עם שני מונים, ניסוח משפט ההיררכיה בזמן, והמסקנה שהמחלקה P מוכלת ממש ב-EXP.
- 4מכונות טיורינג אי-דטרמיניסטיותמחליפים את פונקציית המעברים בפונקציה לקבוצת החזקה, מגדירים ריצה אפשרית והכרעה אי-דטרמיניסטית (מקבלים אם קיימת ריצה מקבלת, ובלבד שכל הריצות עוצרות), מודדים זמן ומקום כמקסימום על פני הריצות, ומקבלים את המחלקות NTime, NSpace, NP ואת השאלה P מול NP.
- 5טיעוני ריפוד ומבוא ל-SATטכניקת הריפוד: ניפוח מלאכותי של הקלט מאפשר להסיק הכלה בין מחלקות מהכלה נתונה אחרת — ומכאן ש-E≠PSPACE ושאם P=NP אז EXP=NEXP; ובחלק השני, ההגדרות הלוגיות של נוסחת CNF, השפה SAT והטענה SAT∈NP.
- 6הגדרה שקולה ל‑NP: אימות, עדים ואישוריםמוכיחים שהמחלקה NP, שהוגדרה באמצעות מכונות אי‑דטרמיניסטיות פולינומיות, שקולה בדיוק למחלקת השפות שעבורן קיים עד (certificate) באורך פולינומי שניתן לאמת בזמן פולינומי — ומראים איך כל אחת משתי ההגדרות נבנית מהשנייה.
- 7CLIQUE ו-Independent Set, רדוקציות בזמן פולינומי, NP-קשה ו-NP-שלמהבשיעור זה מוסיפים שתי שפות גרפים ל-NP (CLIQUE ו-IS), מגדירים את הרדוקציה בזמן פולינומי $\le_p$ ואת המושגים NP-קשה ו-NP-שלמה, ומוכיחים את הרדוקציה בין IS ל-CLIQUE דרך הגרף המשלים — הכלי שיאפשר בהמשך להעשיר את משפחת הבעיות הקשות בלי לחזור להגדרה בכל פעם.
- 8הרדוקציה מ‑SAT ל‑3SATבשיעור מוכיחים SAT ≤p 3SAT על ידי חיתוך כל פסוקית ארוכה לפסוקיות באורך 3 בעזרת משתני עזר חדשים, ומסיקים ש‑3SAT היא NP‑שלמה.
- 9משפט קוק–לויןהשיעור מוכיח את משפט קוק–לוין: SAT היא NP-שלמה, על ידי קידוד טבלת החישוב של מוודא פולינומי כלשהו כנוסחת CNF שבה כל בדיקה היא מקומית — חלון בגודל 2×3.
- 10כיסוי בקודקודים, MAXCUT וצביעת גרפיםמרחיבים את אוסף הבעיות ה-NP-קשות בעזרת שלוש רדוקציות: IS ≤p VC, 3NAE ≤p MAXCUT ו-3NAE ≤p 3COL, מוכיחים ש-2COL ∈ P, ולומדים איך נראית הוכחת נכונות מלאה של רדוקציה בשני הכיוונים.
- 11בעיית SUBSET SUM ושלמותה ב-NPבשיעור מוכיחים ש-SUBSET SUM היא NP-complete באמצעות רדוקציה מ-VC הבונה מספרים ספרה-ספרה כך שלא נוצרות נשאות, ומבחינים בין ערך המספרים לבין אורך הייצוג שלהם — ההבחנה שמסבירה מדוע אלגוריתם התכנון הדינמי מסדר $O(n\cdot S)$ אינו אלגוריתם פולינומי.
- 12PARTITION ו-BIN PACKING, הבעיות ההמילטוניות ו-TSPהשיעור מרחיב את אוסף הבעיות ה-NP-hard בשתי בעיות מספרים — $PARTITION$ ו-$BIN\text{-}PACKING$ — בשרשרת הרדוקציות $SUBSET\text{-}SUM \le_p PARTITION \le_p BIN\text{-}PACKING$, שבה איבר ריפוד יחיד מחושב אלגברית כדי להמיר סכום יעד שרירותי לחלוקה שווה, וממשיך לארבע הבעיות ההמילטוניות ולרדוקציה $UHC \le_p TSP$.
- 13אלגוריתמי קירוב א׳: 2-קירוב ל-VC, ½-קירוב ל-MAXCUT ואי-קירוב של TSPהשיעור הראשון על אלגוריתמי קירוב: אלגוריתם 2-קירוב לכיסוי בקודקודים והוכחת ההידוק שלו, אלגוריתם חיפוש מקומי בעל יחס קירוב ½ ל-MAXCUT, והוכחה שקירוב בכל יחס קבוע לבעיית הסוכן הנוסע הכללית שקול ל-P=NP.
- 14אלגוריתמי קירוב ב׳: ½-קירוב חמדני ל-MAXCUT, 2-קירוב ל-TSP המטרי ו-2-קירוב לאריזה למכליםשלושה אלגוריתמי קירוב פולינומיים, כל אחד עם הוכחת פיזביליות, ניתוח זמן ריצה והוכחת יחס: אלגוריתם חמדני חד-מעברי ביחס ½ ל-MAXCUT, אלגוריתם עץ פורש מינימלי + DFS ביחס 2 לבעיית הסוכן הנוסע כשהמשקלים מקיימים את אי-שוויון המשולש, ואלגוריתם First-Fit ביחס 2 לבעיית האריזה למכלים.
- 15אלגוריתמים אקראיים: מבוא, בעיית המזכיר ואלגוריתם Freivaldsהשיעור מציג את הרעיון של אלגוריתם שמטיל מטבעות — כאשר ההסתברות נלקחת אך ורק על המטבעות הפנימיים של האלגוריתם והקלט נשאר שרירותי ובמקרה הגרוע — ומדגים אותו בשני אלגוריתמים המנותחים עד הסוף: אלגוריתם לבעיית המזכיר שמצליח בהסתברות $\ge \tfrac14$ שם ששום אלגוריתם דטרמיניסטי אינו מבטיח דבר, ואלגוריתם Freivalds לווידוא כפל מטריצות ב-$O(n^2)$ עם טעות חד-צדדית $\le \tfrac12$ שניתן להגבירה ל-$\le 2^{-t}$ ב-$t$ חזרות בלתי תלויות.
- 16מכונות טיורינג אקראיות — הגדרה פורמלית, ומחלקות הסיבוכיות RP, coRP ו-BPPמגדירים פורמלית את מודל החישוב האקראי בשתי צורות שקולות, מגדירים דרכו את משפחת המחלקות $\mathrm{BPP}(\alpha,\beta)$ ואת $\mathrm{RP},\mathrm{coRP},\mathrm{BPP}$, ומוכיחים $\mathrm{RP}\subseteq\mathrm{NP}$, $\mathrm{BPP}\subseteq\mathrm{PSPACE}$ ואת העצמת ההסתברות בטעות חד-צדדית.
- 17העצמת/הקטנת ההסתברות ב-BPP וב-RPמוכיחים שסף השגיאה בהגדרת RP ו-BPP הוא שרירותי: הרצה חוזרת בלתי-תלויה עם 'לפחות פעם אחת' (טעות חד-צדדית) או עם הצבעת רוב (טעות דו-צדדית) מרכזת את ההסתברות ומורידה את השגיאה, כל עוד יש פער של $1/\mathrm{poly}$ מהסף.
- 18בעיית החתך המינימלי: אלגוריתם הכיווץ האקראי, והשיטה ההסתברותיתשיעור בשני חלקים: אלגוריתם אקראי פשוט לבעיית החתך המינימלי — כיווץ קשת אקראית עד שנותרים שני קודקודים — שמחזיר חתך מינימלי ספציפי בהסתברות $\ge 1/\binom{n}{2}$ מעל מטבעות האלגוריתם, ההגברה שלו לחצי ב-$\binom{n}{2}\ln 2$ הרצות, והמסקנה הקומבינטורית שבכל גרף יש לכל היותר $\binom{|V|}{2}$ חתכים מינימליים; ואז השיטה ההסתברותית — הוכחת קיום של חתך בגודל $\ge |E|/2$ ב-$\mathrm{MAXCUT}$ בעזרת לינאריות התוחלת ושתי טענות הסתברותיות בסיסיות.
- 19השיטה ההסתברותית, המשך: ניסוי אחיד ל-MAXCUT, חסם 7/8 ל-3ESAT, ובעיית הקבוצה השלטתשלוש הפעלות של השיטה ההסתברותית ועוד רדוקציה: הוכחה שנייה לקיום חתך בגודל $\ge|E|/2$ — הפעם בבחירת $U$ אחידה מתוך $2^V$ ובספירה קומבינטורית במקום מטבע לכל קודקוד; הוכחה שלכל נוסחת 3E-CNF עם $m$ הסגרים קיימת השמה המספקת לפחות $\tfrac78 m$ מהם; הגדרת בעיית הקבוצה השלטת $\mathrm{DS}$ והוכחת NP-שלמות שלה דרך $\mathrm{VC}\le_p\mathrm{DS}$; ולבסוף טענת קיום מהכיוון ההפוך — בכל גרף בעל דרגה מינימלית $d$ קיימת קבוצה שלטת בגודל לכל היותר $\frac{\ln(d+1)+1}{d+1}|V|$, כולל הגזירה שממנה הגיע ערך ההסתברות.
- 20אלגוריתמים אקראיים לספיקות: אי־שוויון מרקוב, הגברה ודה־רנדומיזציהכיצד הופכים את התוחלת $7m/8$ של מספר הפסוקיות המסופקות בנוסחת 3ECNF לערובה בהסתברות גבוהה — באמצעות אי־שוויון מרקוב והגברה — ואז מסלקים את האקראיות לגמרי בשיטת התוחלות המותנות.
- 21יחס הקירוב 7/8 ל‑MAX‑3ECNF, רדוקציה עצמית של SAT, ו‑coNPהשיעור סוגר את פרק האקראיות: אורז את האלגוריתם הדטרמיניסטי ל‑3ECNF כקירוב ביחס 7/8, משתמש ברדוקציה העצמית של SAT כדי להוכיח שאם SAT ב‑BPP אז NP מוכלת ב‑RP, ופותח את הפרקון על coNP.
- 22MaxIS — הקבוצה הבלתי תלויה המקסימלית: NP-קשה וגם coNP-קשההבעיה $\mathrm{MaxIS}$ שואלת האם הגודל המקסימלי של קבוצה בלתי תלויה בגרף הוא בדיוק $k$; מפני שזו טענת "קיים וגם לכל" היא יוצאת גם NP-קשה (רדוקציה מ-$\mathrm{SAT}$) וגם coNP-קשה (רדוקציה מ-$\overline{\mathrm{IS}}$), ומכאן ש-$\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP}$ אם ורק אם $\mathrm{NP}=\mathrm{coNP}$.
- 23חזרה למבחן א׳: פתרון מטלה 1 ושאלה 1 ממבחן 2שיעור חזרה שכולו פתרון תרגילים: סידור שבע מחלקות סיבוכיות לפי הכלה, המחלקה TISP, שתי ההוכחות ש-NP מוכלת ב-EXP וב-PSPACE, וארבע טענות רדוקציה ממבחן — שלוש מהן עם אלגוריתם שגוי שיש להפריך.
- 24תרגול חזרה: אפיון מחלקות סיבוכיות ביחס ל‑NP (שאלה 3, סעיפים א–ג)שלושה אפיונים שנראים כמעט זהים להגדרת ה‑verifier של NP — היפוך קבלה/דחייה, החלפת 'אם ורק אם' בשני תנאי קיום, וקיצור העד לאורך קבוע — ובכל אחד מהם מכריעים האם המחלקה מכילה את NP, מוכלת בה או שווה לה.
- 25חזרה לקראת המבחן: תת-גרף מקסימלי חסר מעגלים, כיסוי בהיפרגרף 3-אחיד, חתך מכוון ואי-קירוב של Bin-Packingפתרון מלא של ארבעה תרגילים מתרגיל בית 3 — שלושה אלגוריתמי קירוב (½ לתת-גרף חסר מעגלים, 3 לכיסוי בהיפרגרף 3-אחיד, ¼ לחתך מקסימלי בגרף מכוון), רדוקציה $\mathrm{VC}\le_p\mathrm{3H\text{-}VC}$, והוכחה שקיום אלגוריתם קירוב ביחס $1.49$ ל-$\mathrm{BIN\text{-}PACKING}$ גורר $\mathrm{P}=\mathrm{NP}$.
- 26חזרה למבחן ד׳: פתרון מטלה 4 — סגירות BPP לחיתוך, וארבעה אפיונים של המחלקות האקראיותהשיעור האחרון בקורס פותר את מטלה 4: מוכיחים ש‑BPP סגורה לחיתוך (עם העצמה מוקדמת ל‑9/10, כי (2/3)² קטן מחצי), ומכריעים ארבע וריאציות על ההגדרה ההסתברותית — שתיים מהן מתגלות כ‑RP ו‑P, אחת כמחלקת כל השפות, ואחת ככזו ששוויונה ל‑NP שקול לשאלה הפתוחה P=NP.