תורת הסיבוכיות
הועבר על ידי: פרופ' עודד רגב, פרופ' מולי ספרא, פרופ' אמנון תא-שמעקצת על הקורס
הקורס הוא המשך ישיר של מודלים חישוביים. החלק הראשון של הקורס הוא חזרה והעמקה של הנושאים הנלמדים במודלים: המחלקות P, NP, coNP, דוגמאות לבעיות NP-Complete, והקשרים בין המחלקות השונות. לאחר מכן מרחיבים את הדיון גם לסיבוכיות מקום, ולמחלקות רחבות יותר. מתעסקים גם בהשפעת היכולת להשתמש בביטים רנדומיים על המחלקות השונות, כמו גם מחלקות של יכולות קירוב.
