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

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