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

קוד קורס: 10076
2.5 נ"ז

נושאי הקורס:

• מכונות טורינג.
• רדוקציות פשוטות.
• NP ו-P.
• משפט cook.
• בעיות NP קשות ושלמות שונות והרדוקציות המוכיחות זאת.
• מחלקת הסיבוכיות PSPACE.
• אי כריעות בעיית העצירה.
• בעיות לא כריעות אחרות כמו ריצוף המישור.

דרישות הקדם והדרישות המקבילות בקורס חישוביות וסיבוכיות הינן:
דרישות קדם: אוטומטים ושפות פורמליות (10087).
דרישות מקבילות: אין.