סילבוס לקורס סיבוכיות - סמסטר ב 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

סילבוס לקורס סיבוכיות 0368-3168-07

(לא בדיוק לפי סדר ההרצאות).

חזרה והרחבה של חומר שנלמד במודלים:

1.      מכונות טיורינג, NP, לכסון, בעיית העצירה, חיפוש לעומת הכרעה.

2.      מ״ט כמודל אוניפורמי (מכונה אחת לכל קלט) לעומת מעגלים כמודל לא אוניפורמי. כל פונקציה סופית ניתן לחשב במעגל. חסם תחתון משיקולי ספירה למעגלים.

3.      היררכיית זמן.

4.      משפט קוק.

סיבוכיות זכרון:

5.      הגדרות, רדוקציות, הרכבות, דוגמאות: כפל מטריצות, קשירות בגרפים.

6.      מחלקות סיבוכיות

7.      stcon היא NL שלמה, NL ב L^2

8.      NL = coNL

9.      זכרון מוכל בזמן אקספוננציאלי

10.  היררכיית זכרון

11.  הגדרת PSPACE

12.  TQBF: הגדרה והוכחת שלמות ב-PSPACE. קשר למשחקים .

נושאים נוספים הקשורים לזמן וזכרון:

13.  Polynomial Hierarchy

14.  מכונות טיורינג בעלות אוב (oracle Turing machines)

15.  משפט Karp Lipton

אקראיות:

16.  הגדרת BPP,RP .  

17.  דוגמאות לאלגוריתמים מטילי מטבעות: האם AB=C עבור מטריצות.
 estingPolynomial Identity T, Matching בגרף דו-צדדי.

18.  ל־ BPP יש מעגלים בגודל פולינומיאלי.

19.  BPP מוכלת ב 2∑^.

20.  קושי כמשאב:Hardness vs. randomness   

נושאים מתקדמים:

21.  חסמים תחתונים למעגלים בוליאנים

22.  אלגוריתמי קירוב

23.  פרוטוקולים אינטראקטיבים