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

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

משפט: תהיינה $f,g:\mathbb N\to\mathbb N^+$. נניח כי:

1. $g=o(f)$;
2. $f$ ישימה בזמן;
3. $f$ סופר־לינארית, כלומר $f(n)\ge n$ לכל $n\in\mathbb N$.

אז

$$DTime(g)\subsetneq DTime(f^2).$$

הדרכה: השתמשו בשפה

$$T_f= \left\{ \langle M\rangle\#^n \ \middle|\ \begin{array}{l} n\in\mathbb N,\ M\text{ דוחה את }\langle M\rangle\#^n,\\[2pt] time_M(\langle M\rangle\#^n)\le\dfrac{f(|\langle M\rangle\#^n|)}{|\langle M\rangle|} \end{array} \right\}.$$

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