תהאנה A,B Σ* שפות. רדוקציית זמן מעריכי מ A ל B היא מכונת טיורינג דטרמיניסטית M המקיימת את שתי התכונות הבאות. ●…

תהאנה $A,B \subseteq Σ*$ שפות. רדוקציית זמן מעריכי מ A ל B היא מכונת טיורינג דטרמיניסטית M המקיימת את שתי התכונות הבאות. ● קיים $c \ge 1$ כך שלכל $x \in Σ*$ מתקיים $timeM(x) \le O(2^{|x|^c})$. ● לכל $x \in Σ*$ מתקיים $x \in A$ אם ורק אם $M(x) \in B$. עבור כל אחת מהטענות הבאות קבעו האם היא נכונה, שגויה או שקולה לשאלה פתוחה. (12 נק') א. EXP סגורה לרדוקציות זמן פולינומי.