תזכורת: במשפט Savitch נתונה שפה L שכריעה באופן לא דטרמיניסטי ע"י מטל"ד M , שצורכת זיכרון עבודה "סביר" S Ω(log(…

תזכורת: במשפט Savitch נתונה שפה L שכריעה באופן לא דטרמיניסטי ע"י מטל"ד M , שצורכת זיכרון עבודה "סביר" $S \ge Ω(log(n)) (space constructible)$, ועלינו להוכיח, שקיימת מכונה דטרמיניסטית M' , שמכריעה את L וצורכת זיכרון עבודה $Θ(S^2)$ בלבד. (א – 20%) רשמו כיצד פועלת M' על קלט x : ____________________________________________ ____________________________________________ ____________________________________________ ____________________________________________ ____________________________________________ (ב – 40%) הוכיחו בצורה מדויקת כי Space(M',x) ≤ Θ(S^2) : ____________________________________________ ____________________________________________ ____________________________________________ (ג – 40%) הוכיחו בצורה מדויקת כי Time(M',x) ≥ 2^{Θ(S×S)} : ____________________________________________ ____________________________________________ ____________________________________________ 5