תהיינה A,B שפות. רדוקציית זמן מעריכי מ-A ל-B היא מכונת טיורינג M המקיימת: - קיים c 1 כך שלכל x *,

תהיינה $A,B$ שפות. רדוקציית זמן מעריכי מ-$A$ ל-$B$ היא מכונת טיורינג $M$ המקיימת:

• קיים $c\ge1$ כך שלכל $x\in\Sigma^*$, $$time_M(x)\le O(2^{|x|^c});$$
• לכל $x\in\Sigma^*$, $$x\in A\iff M(x)\in B.$$

הוכיחו או הפריכו: $EXP$ סגורה לרדוקציות זמן מעריכי.

רמז: היעזרו בריפוד.