תהי f פונקציה ניתנת לבניית זמן, ותהי g=o(f). נגדיר את שפת האלכסון המרופדת

תהי $f$ פונקציה ניתנת לבניית זמן, ותהי $g=o(f)$. נגדיר את שפת האלכסון המרופדת

$$T_f= \left\{ \langle M\rangle\,1\,0^{,f(|\langle M\rangle|)-|\langle M\rangle|-1} \ \middle|\ M \text{ אינה מקבלת את הקלט בתוך } f(|\langle M\rangle|) \text{ צעדים} \right\}.$$

1. הוכיחו כי $T_f\in DTime(f^2)$.

2. הוכיחו כי $T_f\notin DTime(g)$, והסיקו את משפט היררכיית הזמן.

3. הוכיחו שקיימת שפה ב-$DTime(n^{4051})$ שאינה ב-$DTime(n^{2025})$.

4. עבור כל אחת מן המחלקות הבאות, קבעו אם היא מוכלת ממש ב-$EXP$, שווה ל-$EXP$, מכילה ממש את $EXP$, או שאינה בת-השוואה עמה:

   $DTime(2^{n^6}),$

   $\bigcup_{c\ge1}DTime\left(n^{2^c}\right),$

   $\bigcup_{c\ge1}DTime(c^n),$

   $\bigcup_{c\ge1}DTime\left(c^{n^c}\right),$

   $\bigcup_{c\ge1}DTime\left(n^{n^c}\right).$