סיבוכיות חישוב

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