סילבוס לקורס סיבוכיות - סמסטר ב 2020

פרק 1 (שיעור 1): חזרה והרחבה של חומר שנלמד במודלים

• תזכורות מהקורס במודלים: מ"ט, מ״ט בעלות אוב, מעגלים, NP רדוקציות.
• הכח של חישוב על ידי מעגלים (חישוב לא אוניפורמי)
• משיקולי ספירה יש שפות שלא ניתנות לחישוב, לכסון, בעיית העצירה, היררכיית זמן. חיפוש לעומת הכרעה.
• מ״ט כמודל אוניפורמי לעומת מעגלים כמודל לא אוניפורמי.
• כל פונקציה סופית ניתן לחשב במעגל. חסם תחתון משיקולי ספירה למעגלים.
• משפט קוק, CSAT היא NP שלמה.
• האם DLOG קלה או קשה? האם יש קשר בין קושי לקושי בממוצע?

תרגול: CVAL  היא P שלמה

פרק 2 (שיעורים 2-4): סיבוכיות זכרון

• הגדרות, מחלקות סיבוכיות זיכרון, הררכית זיכרון, יחסים בין זמן וזיכרון,
• רדוקציות, הרכבות,
• דטרמינסטי, לא דטרמניסטי
• הסתברותי?
• דוגמאות: כפל מטריצות, st-con ,A^n,
• st-con היא NL שלמה
• NL מוכלת בL^2
• NL=coNL
• TQBF שלמה ב PSPAC?
• USTCON in RL?

פרק 3 (שיעורים 5-6): משפטי קרפ-ליפטון: לא מחוסר אוניפורמיות תבוא (כנראה) הישועה.

• Poly Time Hierarchy: PH
• קריסה של NP גוררת קריסה של PH
• אם NP מוכל במעגלים בגודל פולינומיאלי, אז ההיררכיה הפולינומיאלית קורסת

פרק 4 (שעורים 7-8): חישוב הסתברותי

• הגדרת RP  ו  BPP
• אמפליפיקציה וצרנוף
• החשיבות של השאלה ״האם P שונה מ BPP״.
• דוגמאות לאלגוריתמים מטילי מטבעות:
  • האם C=AB עבור מטריצות.
  • Polynomial Identity Testing
  • דוגמא לשמוש ב PIT  לאלגוריתם לבדיקת ראשוניות.
  • חתך בגודל חצי + דרנדומיזציה עם p.i.
• משפט: ל BPP יש מעגלים בגודל פולינומיאלי. לא מחישוב הסתברותי תבוא (כנראה) הישועה.
• משפט: BPP מוכלת בהררכיה.

תרגול: זווג מושלם בגרף דו צדדי ומשפט שוורץ-ציפל

פרק 5: אלגוריתמי קירוב ומשפט ה PCP