קורס זה יעסוק בסיבוכיות של בעיות סיפוק אילוצים מכמה היבטים, משפט שפר, המסווג בעיות סיווג אילוצים מעל משתנים בינארים לשני סוגים: פתירות בזמן פולינומי, ו-NP-קשות. תוצאות קושי קירוב הדוקות עבור מספר בעיות: MAX-3LIN, MAX-3SAT, MAX-CUT מבוא לסיבוכיות של הוכחות, וחסמים תחתונים על הפרכה של פסוקיות SAT מקריות. תוצאות למידה: בסיום הקורס הסטודנטיות והסטודנטים יהיו מסוגלים: 1. להגדיר מהי בעיית סיפוק אילוצים. 2. להבחין בין בעיות סיפוק אילוצים שניתן לפתור באופן יעיל לבין כאלה שהן קשות. 3. להכיר טכניקות בסיסיות באלגוריתמי קירוב, ויהיו מסוגלים להפעילן על בעיות חדשות. 4. להכיר טכניקות בסיסיות בהוכחות קושי קירוב, ויהיו מסוגלים להפעילן על בעיות חדשות. 5. להכיר מושגים בסיסיים בסיבוכיות של הוכחות, ואת הקשר לפותרי SAT. 6. להכיר טכניקות בסיסיות בהוכחת חסמים תחתונים על מערכת ההוכחה RESOLUTION, ויהיו מסוגלים להפעיל טכניקות אלה על בעיות חדשות.

פקולטה: מדעי המחשב
|תואר ראשון |תארים מתקדמים
מקצועות קדם

(94412 - הסתברות מ ו- 234247 - אלגוריתמים 1 ו- 236343 - תורת החישוביות)