1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:

בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא $f$ פונקציה ישימה בזמן. נגדיר:

הסימון $\langle M\rangle\#^n$ מבטא קידוד של מכונת טיורינג $M$ ולאחריו $n$ מופעים של התו $\#$.

תהא $g$ פונקציה המקיימת $g=o(f)$.

1. הוכיחו כי $T_f\in DTime(f^2)$.
2. הוכיחו כי $T_f\notin DTime(g)$. הסבירו היכן נעשה שימוש בתוספת $\#^n$ לייצוג המכונה.
3. הסיקו את משפט היררכיית הזמן.

תנו דוגמה לשפה אשר שייכת ל-$DTime(n^{2024})$, אך אינה שייכת ל-$DTime(n^{1011})$.

נתונות שש מחלקות הסיבוכיות:

סדרו את המחלקות בשורה כך שכל מחלקה מכילה את קודמתה. לגבי כל אחת מחמש ההכלות המתקבלות, קבעו אם מדובר בשוויון או בהכלה ממש. הוכיחו את כל טענותיכם.

הוכיחו את הטענות הבאות, תוך שימוש בהגדרה משאלה 2:

1. $TISP^3(2^{n^5},n^7)\subsetneq DTime(2^{n^6})$.
2. $TISP^3(2^{n^8},n^4)\nsubseteq DTime(2^{n^6})$.