סילבוס לקורס סיבוכיות 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.  פרוטוקולים אינטראקטיבים