סיבוכיות

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

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