Lessons
142 handwritten summary pages, alongside 30 transcript files.
Semester B 2026 — the full lessons
Twenty-six lessons rebuilt from two sources: Guy Sofer's handwritten summaries, and the transcripts of the recorded lectures. Each lesson carries the proofs in full, the examples worked in class, and the remarks that were said aloud and never written down.
High confidence
3 medium, 1 low. The rating reflects how many sources corroborate each lesson.
Unrecorded
Lessons 8, 14, 23 were written from the summary alone — no recording of them survives anywhere, and each says so explicitly.
What each file holds
A fixed shape: in brief · background · definitions · theorems and proofs · worked examples · remarks from the lecture · gaps between summary and recording · exam notes. The gaps section is a primary deliverable rather than a footnote — it records mathematical errors corrected in the sources, illegible passages reconstructed, and material that exists in only one source.
These are drafts and have not been checked by a human. The corrections in them are mathematical judgement against handwriting and auto-generated captions — reasoned and documented, but not verified.
Every lesson on one pageDownload as PDFOne continuous run for searching the whole semester, and a real-text PDF to print — typeset in Hebrew, like the lessons themselves.
The lessons
- 1From Computability to Complexity: The Model, the Resources, and the Basic Classesהשיעור מעביר את השאלה המרכזית מ'מה ניתן לחשב' ל'מה ניתן לחשב ביעילות', מקבע את מכונת הטיורינג כסרגל המדידה, מגדיר את משאבי הזמן והמקום, מנתח את מחיר הסימולציות (רב-סרטית והמכונה האוניברסלית), ומוכיח את הקשרים הדו-כיווניים בין זמן למקום ואת ההכלות בין $DTime$ ל-$DSpace$.
- 2Efficient Computation: The Time and Space Classes DTime and DSpaceבשיעור הזה מוגדרות מחלקות הסיבוכיות הבסיסיות $\mathrm{DTime}(f)$ ו-$\mathrm{DSpace}(f)$, נגזרים מהן ההכלות הבסיסיות בין זמן למקום, ומוגדרות המחלקות הגסות P, EXP, PSPACE ו-EXPSPACE.
- 3The Space and Time Hierarchy Theoremsיותר משאב נותן ממש יותר כוח: הוכחת משפט ההיררכיה במקום בלכסון על מכונה אוניברסלית עם שני מונים, ניסוח משפט ההיררכיה בזמן, והמסקנה שהמחלקה P מוכלת ממש ב-EXP.
- 4Nondeterministic Turing Machinesמחליפים את פונקציית המעברים בפונקציה לקבוצת החזקה, מגדירים ריצה אפשרית והכרעה אי-דטרמיניסטית (מקבלים אם קיימת ריצה מקבלת, ובלבד שכל הריצות עוצרות), מודדים זמן ומקום כמקסימום על פני הריצות, ומקבלים את המחלקות NTime, NSpace, NP ואת השאלה P מול NP.
- 5Padding Arguments and an Introduction to SATטכניקת הריפוד: ניפוח מלאכותי של הקלט מאפשר להסיק הכלה בין מחלקות מהכלה נתונה אחרת — ומכאן ש-E≠PSPACE ושאם P=NP אז EXP=NEXP; ובחלק השני, ההגדרות הלוגיות של נוסחת CNF, השפה SAT והטענה SAT∈NP.
- 6An Equivalent Definition of NP: Verification, Witnesses and Certificatesמוכיחים שהמחלקה NP, שהוגדרה באמצעות מכונות אי‑דטרמיניסטיות פולינומיות, שקולה בדיוק למחלקת השפות שעבורן קיים עד (certificate) באורך פולינומי שניתן לאמת בזמן פולינומי — ומראים איך כל אחת משתי ההגדרות נבנית מהשנייה.
- 7CLIQUE and Independent Set, Polynomial-Time Reductions, NP-Hardness and NP-Completenessבשיעור זה מוסיפים שתי שפות גרפים ל-NP (CLIQUE ו-IS), מגדירים את הרדוקציה בזמן פולינומי $\le_p$ ואת המושגים NP-קשה ו-NP-שלמה, ומוכיחים את הרדוקציה בין IS ל-CLIQUE דרך הגרף המשלים — הכלי שיאפשר בהמשך להעשיר את משפחת הבעיות הקשות בלי לחזור להגדרה בכל פעם.
- 8The Reduction from SAT to 3SATבשיעור מוכיחים SAT ≤p 3SAT על ידי חיתוך כל פסוקית ארוכה לפסוקיות באורך 3 בעזרת משתני עזר חדשים, ומסיקים ש‑3SAT היא NP‑שלמה.
- 9The Cook–Levin Theoremהשיעור מוכיח את משפט קוק–לוין: SAT היא NP-שלמה, על ידי קידוד טבלת החישוב של מוודא פולינומי כלשהו כנוסחת CNF שבה כל בדיקה היא מקומית — חלון בגודל 2×3.
- 10Vertex Cover, Max-Cut and Graph Colouringמרחיבים את אוסף הבעיות ה-NP-קשות בעזרת שלוש רדוקציות: IS ≤p VC, 3NAE ≤p MAXCUT ו-3NAE ≤p 3COL, מוכיחים ש-2COL ∈ P, ולומדים איך נראית הוכחת נכונות מלאה של רדוקציה בשני הכיוונים.
- 11SUBSET SUM and its NP-completenessבשיעור מוכיחים ש-SUBSET SUM היא NP-complete באמצעות רדוקציה מ-VC הבונה מספרים ספרה-ספרה כך שלא נוצרות נשאות, ומבחינים בין ערך המספרים לבין אורך הייצוג שלהם — ההבחנה שמסבירה מדוע אלגוריתם התכנון הדינמי מסדר $O(n\cdot S)$ אינו אלגוריתם פולינומי.
- 12PARTITION and BIN PACKING, the Hamiltonian Problems and TSPהשיעור מרחיב את אוסף הבעיות ה-NP-hard בשתי בעיות מספרים — $PARTITION$ ו-$BIN\text{-}PACKING$ — בשרשרת הרדוקציות $SUBSET\text{-}SUM \le_p PARTITION \le_p BIN\text{-}PACKING$, שבה איבר ריפוד יחיד מחושב אלגברית כדי להמיר סכום יעד שרירותי לחלוקה שווה, וממשיך לארבע הבעיות ההמילטוניות ולרדוקציה $UHC \le_p TSP$.
- 13Approximation Algorithms I: A 2-Approximation for Vertex Cover, a ½-Approximation for Max-Cut, and the Inapproximability of TSPהשיעור הראשון על אלגוריתמי קירוב: אלגוריתם 2-קירוב לכיסוי בקודקודים והוכחת ההידוק שלו, אלגוריתם חיפוש מקומי בעל יחס קירוב ½ ל-MAXCUT, והוכחה שקירוב בכל יחס קבוע לבעיית הסוכן הנוסע הכללית שקול ל-P=NP.
- 14Approximation Algorithms II: A Greedy ½-Approximation for Max-Cut, a 2-Approximation for Metric TSP, and a 2-Approximation for Bin Packingשלושה אלגוריתמי קירוב פולינומיים, כל אחד עם הוכחת פיזביליות, ניתוח זמן ריצה והוכחת יחס: אלגוריתם חמדני חד-מעברי ביחס ½ ל-MAXCUT, אלגוריתם עץ פורש מינימלי + DFS ביחס 2 לבעיית הסוכן הנוסע כשהמשקלים מקיימים את אי-שוויון המשולש, ואלגוריתם First-Fit ביחס 2 לבעיית האריזה למכלים.
- 15Randomized Algorithms: Introduction, the Secretary Problem and Freivalds' Algorithmהשיעור מציג את הרעיון של אלגוריתם שמטיל מטבעות — כאשר ההסתברות נלקחת אך ורק על המטבעות הפנימיים של האלגוריתם והקלט נשאר שרירותי ובמקרה הגרוע — ומדגים אותו בשני אלגוריתמים המנותחים עד הסוף: אלגוריתם לבעיית המזכיר שמצליח בהסתברות $\ge \tfrac14$ שם ששום אלגוריתם דטרמיניסטי אינו מבטיח דבר, ואלגוריתם Freivalds לווידוא כפל מטריצות ב-$O(n^2)$ עם טעות חד-צדדית $\le \tfrac12$ שניתן להגבירה ל-$\le 2^{-t}$ ב-$t$ חזרות בלתי תלויות.
- 16Randomized Turing Machines: the Formal Model, RP, coRP and BPPמגדירים פורמלית את מודל החישוב האקראי בשתי צורות שקולות, מגדירים דרכו את משפחת המחלקות $\mathrm{BPP}(\alpha,\beta)$ ואת $\mathrm{RP},\mathrm{coRP},\mathrm{BPP}$, ומוכיחים $\mathrm{RP}\subseteq\mathrm{NP}$, $\mathrm{BPP}\subseteq\mathrm{PSPACE}$ ואת העצמת ההסתברות בטעות חד-צדדית.
- 17Error Amplification for BPP and RPמוכיחים שסף השגיאה בהגדרת RP ו-BPP הוא שרירותי: הרצה חוזרת בלתי-תלויה עם 'לפחות פעם אחת' (טעות חד-צדדית) או עם הצבעת רוב (טעות דו-צדדית) מרכזת את ההסתברות ומורידה את השגיאה, כל עוד יש פער של $1/\mathrm{poly}$ מהסף.
- 18Minimum Cut: the Randomized Contraction Algorithm, and the Probabilistic Methodשיעור בשני חלקים: אלגוריתם אקראי פשוט לבעיית החתך המינימלי — כיווץ קשת אקראית עד שנותרים שני קודקודים — שמחזיר חתך מינימלי ספציפי בהסתברות $\ge 1/\binom{n}{2}$ מעל מטבעות האלגוריתם, ההגברה שלו לחצי ב-$\binom{n}{2}\ln 2$ הרצות, והמסקנה הקומבינטורית שבכל גרף יש לכל היותר $\binom{|V|}{2}$ חתכים מינימליים; ואז השיטה ההסתברותית — הוכחת קיום של חתך בגודל $\ge |E|/2$ ב-$\mathrm{MAXCUT}$ בעזרת לינאריות התוחלת ושתי טענות הסתברותיות בסיסיות.
- 19The Probabilistic Method, Continued: Uniform Sampling for MAXCUT, the 7/8 Bound for E3SAT, and Dominating Setשלוש הפעלות של השיטה ההסתברותית ועוד רדוקציה: הוכחה שנייה לקיום חתך בגודל $\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|$, כולל הגזירה שממנה הגיע ערך ההסתברות.
- 20Randomized Algorithms for Satisfiability: Markov's Inequality, Amplification and Derandomizationכיצד הופכים את התוחלת $7m/8$ של מספר הפסוקיות המסופקות בנוסחת 3ECNF לערובה בהסתברות גבוהה — באמצעות אי־שוויון מרקוב והגברה — ואז מסלקים את האקראיות לגמרי בשיטת התוחלות המותנות.
- 21The 7/8 Approximation Ratio for MAX-3ECNF, Self-Reducibility of SAT, and coNPהשיעור סוגר את פרק האקראיות: אורז את האלגוריתם הדטרמיניסטי ל‑3ECNF כקירוב ביחס 7/8, משתמש ברדוקציה העצמית של SAT כדי להוכיח שאם SAT ב‑BPP אז NP מוכלת ב‑RP, ופותח את הפרקון על coNP.
- 22MaxIS — Maximum Independent Set: NP-hard and coNP-hardהבעיה $\mathrm{MaxIS}$ שואלת האם הגודל המקסימלי של קבוצה בלתי תלויה בגרף הוא בדיוק $k$; מפני שזו טענת "קיים וגם לכל" היא יוצאת גם NP-קשה (רדוקציה מ-$\mathrm{SAT}$) וגם coNP-קשה (רדוקציה מ-$\overline{\mathrm{IS}}$), ומכאן ש-$\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP}$ אם ורק אם $\mathrm{NP}=\mathrm{coNP}$.
- 23Exam Review I: Assignment 1 and Exam 2 Question 1שיעור חזרה שכולו פתרון תרגילים: סידור שבע מחלקות סיבוכיות לפי הכלה, המחלקה TISP, שתי ההוכחות ש-NP מוכלת ב-EXP וב-PSPACE, וארבע טענות רדוקציה ממבחן — שלוש מהן עם אלגוריתם שגוי שיש להפריך.
- 24Exam Review: Characterising Complexity Classes Relative to NP (Question 3, parts a–c)שלושה אפיונים שנראים כמעט זהים להגדרת ה‑verifier של NP — היפוך קבלה/דחייה, החלפת 'אם ורק אם' בשני תנאי קיום, וקיצור העד לאורך קבוע — ובכל אחד מהם מכריעים האם המחלקה מכילה את NP, מוכלת בה או שווה לה.
- 25Exam Review III: Maximum Acyclic Subgraph, Vertex Cover in 3-Uniform Hypergraphs, Directed Max-Cut, and the Inapproximability of Bin Packingפתרון מלא של ארבעה תרגילים מתרגיל בית 3 — שלושה אלגוריתמי קירוב (½ לתת-גרף חסר מעגלים, 3 לכיסוי בהיפרגרף 3-אחיד, ¼ לחתך מקסימלי בגרף מכוון), רדוקציה $\mathrm{VC}\le_p\mathrm{3H\text{-}VC}$, והוכחה שקיום אלגוריתם קירוב ביחס $1.49$ ל-$\mathrm{BIN\text{-}PACKING}$ גורר $\mathrm{P}=\mathrm{NP}$.
- 26Exam Review IV: Assignment 4 — Closure of BPP under Intersection, and Four Variants of the Randomized Classesהשיעור האחרון בקורס פותר את מטלה 4: מוכיחים ש‑BPP סגורה לחיתוך (עם העצמה מוקדמת ל‑9/10, כי (2/3)² קטן מחצי), ומכריעים ארבע וריאציות על ההגדרה ההסתברותית — שתיים מהן מתגלות כ‑RP ו‑P, אחת כמחלקת כל השפות, ואחת ככזו ששוויונה ל‑NP שקול לשאלה הפתוחה P=NP.