סילבוס

תוכן הקורס ומטרתו

מטרת הקורס לשמש כמבוא לסבוכיות חישובית. אנו נלמד איך לסווג שפות לפי סבוכיות הזמן והמקום שלהם, ולפי תכונות מתמטיות כמו היכולת להוכיח שייכות בשפה לבודק חלש (כגון המחלקות NP,IP, PCP). אנו נראה כיצד המסגרת התאורטית נותנת נקודת מבט חדשה ומועילה על בעיות מעשיות בעלות חשיבות מרכזית, כגון בעיות NP שלמות, אלגוריתמי קירוב לבעיות אלו, והוכחת קושי של קירוב.

בקורס שלושה חלקים:

1. רקע ובסיס:

מכונות טיורינג, מעגלים בוליאניים, חישוב אוניפורמי ולא אוניפורמי. לכסון. בעית העצירה. הררכית זמן. מכונות אורקל ומגבלות טיעוני הלכסון. מכונות מוגבלות זכרון. הרכבה של מכונות מוגבלות זכרון. רדוקציות LogSpace.
CVAL היא P-שלמה. CSAT היא NP-שלמה. NL. STCON היא NL-שלמה. משפט סויץ. משפט אימרמן.

2. אלגוריתמים הסתברותיים. משפט שוורץ-ציפל. חסמי צרנוף. ל BPP מעגלים פולינומיים. ההררכיה הפולינומית. BPP מוכלת ברמה השניה של ההררכיה. משפט קרפ-ליפטון. הוכחות אינטראקטיביות, MA, AM, IP. המחלקה coNP מוכלת ב IP.

3. אלגוריתמי קירוב. דוגמאות. קירוב על ידי אלגוריתם חמדן. קירוב על ידי ריכוך של בעיית אופטימזציה. קושי של קירוב. בעיות פער. רדוקציות משמרות פער. משפט ה PCP (ללא הוכחה). הקשר בין משפט ה PCP לקושי של קירוב.