משפטים ודברים לזכור

הוכחה: יהי $A$ קבוצת התאים ש-$M$ כתבה בהם. לכל תא ב-$A$ מתאימים את הצעד הראשון שבו נכתב; זו פונקציה חד-חד-ערכית מ-$A$ ל-$\{1,\dots,\mathrm{TIME}_M(x)\}$, ולכן $|A|\le \mathrm{TIME}_M(x)$. אינטואיציה: כל צעד כותב לכל היותר תא אחד, ולעיתים כותב בתא שכבר נכתב.

השורה התחתונה שכדאי לזכור: במקום — שקילות עד כדי סדר גודל; בזמן — לכל היותר ריבוע. ההוכחה מגדילה את הא"ב כך שכל תא מחזיק $k$-יה של תווים; האוברהד לכל צעד מסומלץ הוא סריקה של כל התאים שנכתבו כדי לאתר ולעדכן את $k$ הראשים.

השורה התחתונה לזכור: בזמן — כל צעד מוכפל באורך קידוד המכונה; במקום — כל תו מוכפל ב-$\log$ של גודל א"ב המכונה. שלב האתחול (העתקת $\langle M\rangle$ ו-$x$) נבלע בדרך כלל, בהנחה ש-$M$ קוראת את כל הקלט ולכן $\mathrm{TIME}_M(x)\ge|x|$ — אבל זו הנחה שצריך לומר בקול.

הקבוע תלוי במכונה בלבד. החסם אינו הדוק — בדרך הגדלנו כל מחובר כדי לחלץ את SPACE כגורם משותף. השורה התחתונה: חסם על המקום + עצירה $\Rightarrow$ חסם על הזמן.

ההוכחה: אם $A\in\mathrm{DTIME}(f)$ אז יש $M$ המכריעה את $A$ וקבוע $c$ כך ש-$\mathrm{TIME}_M(x)\le c\cdot f(|x|)$. אותה מכונה עובדת גם עבור המקום, כי $\mathrm{SPACE}_M(x)\le \mathrm{TIME}_M(x)\le c\cdot f(|x|)$.

ההוכחה: $M$ מכריעה ולכן עוצרת, אז $\mathrm{TIME}_M(x)\le 2^{c'\cdot \mathrm{SPACE}_M(x)}$; ומכיוון ש-$\mathrm{SPACE}_M(x)\le c\cdot f(|x|)$, מקבלים $\mathrm{TIME}_M(x)\le 2^{c'c\cdot f(|x|)}$, כלומר הקבוע הוא מכפלת שני הקבועים, $d = c'\cdot c$.

המקדם 4 מגיע מארבעה סוויפים על תוכן כל הסרטים לכל צעד מסומלץ. שימו לב לכיוון: אי-השוויון אינו אומר שחד-סרטית טובה יותר, אלא שהיא "לא הרבה יותר גרועה" — הכפל ב-SPACE יכול להיות משמעותי מאוד.

הזמן: על כל צעד של $M$ האוניברסלית סורקת את כל טבלת $\delta$, ולכן משלמת פקטור $|\langle M\rangle|$. המקום: $M_U$ עובדת בבינארית, ולכן כל תו של $\Gamma$ עולה לה $\log|\Gamma|$ ביטים.

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

מתקבל מספירת הקונפיגורציות: $|Q|\cdot|\Gamma|^{s}\cdot s \le 2^{s(\log|Q| + \log|\Gamma| + 1)}$, ולכן $c = \log|Q| + \log|\Gamma| + 1$ — קבוע התלוי רק במכונה. החסם אינו הדוק: בדרך התעלמנו מביטוי שיכול להיות גדול מאוד, ולכן ייתכן שהזמן קטן בהרבה. המרצה מסמן שלפעמים נרצה לחזור לנקודה הזו כשה-SPACE גדול.

השרשור: $M$ מכריעה $\Rightarrow$ עוצרת על כל $x$ $\Rightarrow$ $\mathrm{TIME}_M(x)\le 2^{(\log|Q|+\log|\Gamma|+1)\cdot \mathrm{SPACE}_M(x)}\le 2^{(\log|Q|+\log|\Gamma|+1)\cdot c\cdot f(|x|)}$. $\hat c=1$ כי אין מקדם לפני החזקה.

ההוכחה: פורסים את $f=O(g)$ כדי לקבל את הקבוע $c$, פורסים את $A\in\mathrm{DTIME}(f)$ כדי לקבל $M$ ואת $\hat c$, ומגדירים את הקבוע החדש $\tilde c = \hat c\cdot c$. שוב: הקבוע החדש בנוי רק מקבועים שכבר הושגו.

ההוכחה הקצרה: $A\in\mathrm{P}$ $\Rightarrow$ קיים $c$ עם $A\in\mathrm{DTIME}(n^{c})$ $\Rightarrow$ מהטענה $\mathrm{DTIME}(f)\subseteq\mathrm{DSPACE}(f)$ נקבל $A\in\mathrm{DSPACE}(n^{c})$ $\Rightarrow$ $A\in\mathrm{PSPACE}$. המרצה הוכיח קודם את הגרסה הארוכה במכוון, כתרגול בפירוק והרכבה של פרמטרים.

ההוכחה: אותה מכונה, והקבוע החדש הוא מכפלת שני הקבועים $d = c'\cdot c$. המרצה עוצר על שאלת סטודנט — האם המכפלה של שני קבועים חיוביים בהכרח עובדת — ומראה שכן, כי פשוט משרשרים את שני אי-השוויונות.