מטל"ד M , שצורכת זיכרון עבודה "סביר" (S Ω(log(n))) (space constructible), ועלינו להוכיח, שקיימת מכונה דטרמיניס…

מטל"ד M , שצורכת זיכרון עבודה "סביר" $(S \ge Ω(log(n))) (space constructible)$, ועלינו להוכיח, שקיימת מכונה דטרמיניסטית מתאימה M' , שמכריעה את L . קבעו אילו מהטענענת הבאות (i,ii,iii) אודות המכונה הדטרמיניסטית M' הינן נכונות. (i) זמן הריצה של המכונה M' מקיים $Time(M',x) \ge 2^{Θ(S\times S)} . (ii)$ המכונה M' רושמת במהלך הריצה שלה את גרף הקונפיגורציות $G_{M,x}$ של החישוב M(x) . (iii) זיכרון העבודה של המכונה M' מקיים $Space(M',x) \le Θ(S^2)$ .