2Efficient Computation: The Time and Space Classes DTime and DSpace

בקצרה

• מגדירים כאן, לראשונה בקורס, מחלקות סיבוכיות: $\mathrm{DTime}(f)$ ו-$\mathrm{DSpace}(f)$ — קבוצות של שפות (לא של מכונות) שניתן להכריע בזמן $O(f)$ או במקום $O(f)$ בהתאמה.
• מוכיחים שני הקשרים הבסיסיים בין זמן למקום ברמת המחלקות: $\mathrm{DTime}(f)\subseteq \mathrm{DSpace}(f)$ (מקום זול מזמן), ו-$\mathrm{DSpace}(f)\subseteq\bigcup_{d\ge 1}\mathrm{DTime}(2^{d\cdot f})$ (זמן חסום אקספוננציאלית במקום — אבל רק כשהמכונה עוצרת).
• מוכיחים שהמחלקות מונוטוניות ביחס לסדר גודל: אם $f=O(g)$ אז $\mathrm{DTime}(f)\subseteq\mathrm{DTime}(g)$ וכן ל-$\mathrm{DSpace}$. זה מה שהופך את הכתיב $\mathrm{DTime}(n^2)$ למשמעותי.
• מגדירים את ארבע המחלקות הגסות של הקורס: $P$, $\mathrm{EXP}$, $\mathrm{PSPACE}$, $\mathrm{EXPSPACE}$, כאיחודים אינסופיים של מחלקות עדינות.
• מוכיחים $P\subseteq \mathrm{PSPACE}$ (פעמיים: הוכחה "ארוכה" שמפרקת את כל הפרמטרים, והוכחה בת שתי שורות מהטענות הקודמות), ובהקלטה השנייה גם $\mathrm{PSPACE}\subseteq \mathrm{EXP}$.
• המסר המתודי של השיעור, וכנראה החשוב שבו: בסיבוכיות ההוכחות אינן קשות אלא עתירות פרמטרים. כל ההוכחות כאן נבנות באותו מבנה קשיח — פורסים הגדרה כדי לקבל ליד מכונה וקבועים, ואז מרכיבים מהם קבועים חדשים. מי ששולט במבנה הזה לא ייתקע בהוכחות הכבדות של שיעור 3 ואילך.

רקע ותלויות

כל החומר של השיעור הזה נשען על שיעור 1 בלבד (ראו שיעור 1). מה שצריך להיות ביד:

1. גדלי הסיבוכיות של ריצה בודדת. עבור מכונת טיורינג $M$ ומילה $x\in\Sigma_M^*$:

• $\mathrm{time}_M(x)$ — מספר הצעדים ש-$M$ מבצעת בריצה על $x$ (ואינסוף אם אינה עוצרת).
• $\mathrm{space}_M(x)$ — מספר התאים השונים ש-$M$ כותבת עליהם במהלך הריצה על $x$.

שימו לב שאלה גדלים של ריצה בודדת — הם פונקציה של $x$, לא של $n$. בשיעור 1 לא הגדרנו שום מחלקה של שפות; זה בדיוק מה שנעשה היום. (שאלה שנשאלה בשיעור, [00:06:33]: "מה ההבדל בין $\mathrm{DSpace}$ למה שעשינו בשיעור הקודם?" — בשיעור הקודם הגדרנו את המקום של מכונה, לא מחלקה של שפות המקיימות משהו.)

2. ההסכמה על מודל המכונה. אלא אם נאמר אחרת, "מכונה" בקורס הזה פירושה מכונת טיורינג דטרמיניסטית חד-סרטית סטנדרטית — כזו שהראש שלה אינו עוצר במקום ואין בה שום וריאנט מיוחד ([00:43:50]). זה חשוב מאוד: חסמי זמן קונקרטיים (למשל $n^2$ עבור פלינדרומים) תלויים במודל.

3. הקשר בין זמן למקום ברמת הריצה הבודדת. זו התוצאה המרכזית של שיעור 1, והשיעור הזה נפתח בה (עמוד 1 בסיכום). היא מנוסחת ומוכחת במלואה למטה כמשפט 1, כי כל שאר השיעור נשען עליה.

4. סימון $O$ גדול. ההגדרה המקורית: $f=O(g)$ אם קיימים $c>0$ ו-$n_0\in\mathbb{N}$ כך שלכל $n>n_0$ מתקיים $f(n)\le c\cdot g(n)$. ראינו במבנה נתונים שאפשר לוותר על $n_0$ ולדרוש את החסם לכל $n\in\mathbb{N}$, במחיר קבוע אחר ([00:53:05], וגם [00:05:11] בהקלטה השנייה). הגרסה בלי $n_0$ היא זו שנשתמש בה, והיא זו שמתאימה להגדרת $\mathrm{DTime}$ — שדורשת חסם לכל $x$, לא רק מאורך מסוים והלאה.

5. מכריעה $\Rightarrow$ עוצרת. אם $M$ מכריעה שפה $A$ אז $M$ עוצרת על כל קלט. זו הנקודה שתאפשר לנו להפעיל את משפט 1 בתוך ההוכחות.

הגדרות

הגדרה 1: $\mathrm{DTime}(f)$

תהא $f:\mathbb{N}\to\mathbb{N}$ פונקציה כלשהי. נגדיר:

$\mathrm{DTime}(f)=\Big\{\,A \;\Big|\; \exists M\ \exists c>0 \ \text{ s.t. }\ M \text{ decides } A \ \wedge\ \forall x:\ \mathrm{time}_M(x)\le c\cdot f(|x|)\,\Big\}$

כלומר: $A\in\mathrm{DTime}(f)$ אם ורק אם קיימת מכונה $M$ וקיים קבוע $c>0$ כך ש-$M$ מכריעה את $A$ וגם לכל $x$ מתקיים $\mathrm{time}_M(x)\le c\cdot f(|x|)$.

ה-$D$ הוא קיצור ל-Deterministic — בהמשך הקורס יופיעו גם מכונות אי-דטרמיניסטיות, אך כרגע כל המכונות שלנו דטרמיניסטיות.

אינטואיציה. $\mathrm{DTime}(f)$ היא אוסף כל השפות שניתן להכריע בזמן $O(f)$. זו הדרך הנכונה לחשוב על המחלקה, אבל לא הדרך לעבוד איתה: כשבאים להוכיח משהו חייבים לרדת להגדרה הפורמלית, כי רק היא נותנת ליד את המכונה ואת הקבוע ([00:04:28]).

שלוש נקודות דיוק שחזרו שוב ושוב בשיעור:

1. סדר הכמתים. $\exists M\,\exists c\,\forall x$ — המכונה והקבוע נבחרים ראשונים, ורק אחר כך רצים על כל הקלטים. קבוע אחד משרת את כל הקלטים.
2. $f$ מקבלת $|x|$ ולא $x$. $f$ היא פונקציה מ-$\mathbb{N}$ ל-$\mathbb{N}$, ו-$x$ הוא מחרוזת; $f(x)$ חסר משמעות. סיבוכיות תמיד נמדדת ביחס לאורך הקלט ([00:14:41]).
3. האיברים של המחלקה הם שפות. $A$ אינה מכונת טיורינג — מחלקות סיבוכיות הן קבוצות שאיבריהן שפות ([00:17:26]).

דוגמה. $PAL$, שפת הפלינדרומים מעל $\{0,1\}$, מקיימת $PAL\in\mathrm{DTime}(n^2)$ — ראו את הפירוט בסעיף הדוגמאות.

אי-דוגמה שממחישה את הגבול. שפה שאינה כריעה כלל, למשל $\mathrm{HALT}$, אינה שייכת ל-$\mathrm{DTime}(f)$ עבור שום $f$ — ההגדרה דורשת ש-$M$ תכריע את $A$, לא רק תקבל אותה. חסם זמן בלי דרישת הכרעה הוא חסר תוכן כאן.

הגדרה 2: $\mathrm{DSpace}(f)$

תהא $f:\mathbb{N}\to\mathbb{N}$. נגדיר:

$\mathrm{DSpace}(f)=\Big\{\,A \;\Big|\; \exists M\ \exists c>0 \ \text{ s.t. }\ M \text{ decides } A \ \wedge\ \forall x:\ \mathrm{space}_M(x)\le c\cdot f(|x|)\,\Big\}$

ההגדרה זהה מילה במילה להגדרה 1, למעט החלפת $\mathrm{time}$ ב-$\mathrm{space}$.

אינטואיציה. כל השפות שניתן להכריע במקום $O(f)$.

דוגמה. $PAL\in\mathrm{DSpace}(n)$ — האלגוריתם הנאיבי כותב רק על תאי הקלט עצמו, כלומר $\mathrm{space}_M(x)\le|x|$, ולכן מתאים $c=1$ ו-$f(n)=n$.

הגדרה 3: $f=O(g)$ (בגרסה שנשתמש בה)

$f=O(g)$ אם קיים $c>0$ כך שלכל $n\in\mathbb{N}$ מתקיים $f(n)\le c\cdot g(n)$.

זו גרסה שקולה לגרסה הסטנדרטית (שבה החסם נדרש רק החל מ-$n_0$ כלשהו), והשקילות נראתה בקורס מבנה נתונים. השקילות אינה מובנת מאליה והיא הכרחית כאן: הגדרות 1–2 דורשות את החסם לכל $x$, גם לקלטים קצרים מאוד, בעוד הגדרת ה-$O$ המקורית "מוותרת" על קלטים קצרים. הרעיון שמאחורי השקילות: יש רק מספר סופי של קלטים באורך $\le n_0$, ולכן אפשר להגדיל את הקבוע $c$ כך שיבלע גם אותם.

הגדרה 4: המחלקות הגסות $P,\ \mathrm{EXP},\ \mathrm{PSPACE},\ \mathrm{EXPSPACE}$

$P=\bigcup_{c\ge 1}\mathrm{DTime}(n^c)\qquad \mathrm{EXP}=\bigcup_{c\ge 1}\mathrm{DTime}(2^{n^c})$ $\mathrm{PSPACE}=\bigcup_{c\ge 1}\mathrm{DSpace}(n^c)\qquad \mathrm{EXPSPACE}=\bigcup_{c\ge 1}\mathrm{DSpace}(2^{n^c})$

מינוח. המחלקות $\mathrm{DTime}(f)$ ו-$\mathrm{DSpace}(f)$ נקראות מחלקות עדינות (fine), כיוון שכל מחלקה כזו מוגדרת על פי פונקציית חסם אחת ספציפית. המחלקות שבהגדרה זו נקראות מחלקות גסות (coarse), והן איחודים אינסופיים של מחלקות עדינות.

אינטואיציה. $P$ היא אוסף כל השפות שניתן להכריע בזמן פולינומי בגודל הקלט. חשוב לומר "בגודל הקלט" — ל"פולינומי" סתם אין משמעות ([01:06:29]). הנקודה העדינה: החזקה $c$ היא קבועה ואינה תלויה בקלט; יש פולינום אחד שחוסם את זמן הריצה על כל הקלטים.

מה הולך לאיבוד באיחוד. שייכות לאיחוד היא טענת קיום: $A\in P$ פירושו "קיים $c\ge 1$ כך ש-$A\in\mathrm{DTime}(n^c)$". כשמוכיחים שייכות ל-$P$ חייבים "לקלף" קודם את הקיים הזה, ורק אז מגיעים למכונה ([01:09:40]).

דוגמה. $PAL\in\mathrm{DTime}(n^2)\subseteq P$.

אי-דוגמה שמחדדת את הגבול. $\mathrm{DTime}(n^{100})\subseteq P$ — למרות שאלגוריתם בזמן $n^{100}$ אינו ישים בפועל בשום צורה. $P$ היא מחלקה רחבה מאוד, והזיהוי שלה עם "יעיל" הוא הסכמה, לא משפט (ראו הערות).

משפטים והוכחות

משפט 1: הקשר בין זמן למקום (תזכורת משיעור 1, עם ההוכחה במלואה)

חלק א'. לכל מכונה $M$ ולכל $x\in\Sigma_M^*$: $\ \mathrm{space}_M(x)\le \mathrm{time}_M(x)$.

חלק ב'. לכל מכונה $M$ קיים $c>0$ כך שלכל $x\in\Sigma_M^*$: אם $M$ עוצרת על $x$ אז $\mathrm{time}_M(x)\ \le\ 2^{\,c\cdot \mathrm{space}_M(x)},\qquad c=\lg|Q|+\lg|\Gamma|+1 .$

כאן $Q$ היא קבוצת המצבים של $M$ ו-$\Gamma$ אלפבית הסרט שלה.

הוכחת חלק א'. בכל צעד יחיד המכונה כותבת על תא אחד לכל היותר. לכן מספר התאים השונים שנכתבו לאורך הריצה אינו עולה על מספר הצעדים. $\square$

הוכחת חלק ב'. נסמן $s=\mathrm{space}_M(x)\ge 1$. נספור את מספר הקונפיגורציות השונות האפשריות בריצה של $M$ על $x$. קונפיגורציה נקבעת על ידי שלושה רכיבים:

1. המצב הנוכחי — $|Q|$ אפשרויות;
2. תוכן התאים שנכתבו — כל אחד מ-$s$ התאים מכיל אות מ-$\Gamma$, כלומר $|\Gamma|^{s}$ אפשרויות;
3. מיקום הראש — $s$ אפשרויות.

לכן מספר הקונפיגורציות השונות חסום על ידי $|Q|\cdot|\Gamma|^{s}\cdot s \;=\; 2^{\,\lg|Q|\;+\;s\cdot\lg|\Gamma|\;+\;\lg s}.$

כעת נחסום כל אחד משלושת המחוברים במעריך בביטוי שהוא ליניארי ב-$s$, ובכך "נשטח" את המעריך:

• $\lg|Q|\le s\cdot\lg|Q|$, כי $s\ge 1$;
• $s\cdot\lg|\Gamma|$ — כבר ליניארי ב-$s$;
• $\lg s\le s$, כי $\lg s\le s$ לכל $s\ge 1$.

מכאן שמספר הקונפיגורציות חסום על ידי $2^{(\lg|Q|+\lg|\Gamma|+1)\cdot s}=2^{c\cdot s}$.

לבסוף: $M$ דטרמיניסטית, ולכן אם היא מגיעה פעמיים לאותה קונפיגורציה היא נכנסת ללולאה אינסופית ואינה עוצרת. בהנחה ש-$M$ עוצרת על $x$, כל הקונפיגורציות בריצה שונות זו מזו, ולכן מספר הצעדים אינו עולה על מספר הקונפיגורציות האפשריות: $\mathrm{time}_M(x)\le 2^{c\cdot \mathrm{space}_M(x)}. \qquad\square$

הערה: בהרצאה זה נאמר בקיצור ("בעזרת טיעון על מספר קונפיגורציות"); הפירוט כאן. במיוחד, המעבר $\lg s\le s$ ו-$\lg|Q|\le s\lg|Q|$ הוא בדיוק המקום שבו הקבוע $c$ מקבל את הצורה $\lg|Q|+\lg|\Gamma|+1$.

שני ההסברים שנוספו בסיכום לצד המשפט (עמוד 1):

① למה צריך את ההנחה "$M$ עוצרת". בלעדיה הטענה שקרית לחלוטין, ולא רק כי הקבוע לא מספיק: הזמן אינו חסום על ידי שום פונקציה של המקום. הדוגמה שניתנה בשיעור ([00:00:35]): מכונה שרצה לנצח על שני תאים בלבד. המקום הוא $2$, אבל אין שום פונקציה $g$ שתקיים $\mathrm{time}\le g(2)$, כי הזמן אינסופי. שימו לב שהכיוון ההפוך (חלק א') נכון תמיד, ללא שום הנחה.

② סדר הכמתים ב-$c$. הקבוע $c$ תלוי אך ורק במכונה ($|Q|$ ו-$|\Gamma|$ שלה) ואינו תלוי בקלט $x$ — ולכן ניתן "להוציא אותו החוצה" לפני ה-$\forall x$. זו נקודה שתחזור לרדוף אותנו בשיעור 3: כשהמכונה עצמה היא הקלט לבעיה, "קבוע התלוי במכונה" הופך פתאום לקבוע התלוי בקלט, והמשפט הזה כבר לא מספיק ([01:03:25] בהקלטה השנייה).

הערת דיוק חשובה ([00:01:08]): החסם $2^{c\cdot s}$ אינו הדוק. השטחנו כאן שלושה מחוברים שונים לאותה צורה. בהמשך הקורס נצטרך לחזור לחישוב מספר הקונפיגורציות ולחסום אותו אחרת — למשל כשה-$\mathrm{space}$ גדול מאוד, או כשרוצים חסם שאינו תלוי במכונה כלל.

משפט 2: $\mathrm{DTime}(f)\subseteq \mathrm{DSpace}(f)$

לכל $f:\mathbb{N}\to\mathbb{N}$ מתקיים $\mathrm{DTime}(f)\subseteq\mathrm{DSpace}(f)$.

הוכחה. תהא $f:\mathbb{N}\to\mathbb{N}$. תהא $A\in\mathrm{DTime}(f)$.

מהגדרת $\mathrm{DTime}(f)$: קיימת מכונה $M$ וקיים $c>0$ כך ש-$M$ מכריעה את $A$, וגם לכל $x$ מתקיים $\mathrm{time}_M(x)\le c\cdot f(|x|)$.

נוכיח ש-$A\in\mathrm{DSpace}(f)$, כלומר: נראה שקיימת מכונה $M'$ וקיים $c'>0$ כך ש-$M'$ מכריעה את $A$ וגם לכל $x$ מתקיים $\mathrm{space}_{M'}(x)\le c'\cdot f(|x|)$.

• נתבונן ב-$M$ (אותה מכונה — אין צורך בבנייה חדשה).
• נתבונן ב-$c$; אכן $c>0$.
• אכן $M$ מכריעה את $A$ (זה בדיוק מה שנתון).
• יהי $x$. לפי משפט 1 חלק א', $\mathrm{space}_M(x)\ \le\ \mathrm{time}_M(x)\ \le\ c\cdot f(|x|).$

לכן $A\in\mathrm{DSpace}(f)$, ומכיוון ש-$A$ נבחרה שרירותית, $\mathrm{DTime}(f)\subseteq\mathrm{DSpace}(f)$. $\square$

למה ההוכחה נראית "חזרתית" ובכל זאת כתובה כך. המרצה עמד על כך שגם כשההוכחה טריוויאלית, כותבים את כל חלקי ההגדרה — כולל "אכן $c>0$" ו"אכן $M$ מכריעה את $A$" ([00:11:32], [01:01:32]). הסיבה אינה פדנטיות: המקום שבו כתבנו "$M$ מכריעה את $A$" כנתון והמקום שבו אנחנו נדרשים לזה כמסקנה הם שני מקומות שונים בהוכחה. בהוכחות הכבדות של הקורס (משפטי ההיררכיה, קוק–לוין) המבנה הזה הוא מה שמונע אובדן פרמטרים.

משפט 3: $\mathrm{DSpace}(f)\subseteq\bigcup_{d\ge 1}\mathrm{DTime}\!\left(2^{d\cdot f}\right)$

לכל $f:\mathbb{N}\to\mathbb{N}$ מתקיים $\mathrm{DSpace}(f)\ \subseteq\ \bigcup_{d\ge 1}\mathrm{DTime}\!\left(2^{\,d\cdot f}\right).$

הכוונה ב-$2^{d\cdot f}$ היא לפונקציה $n\mapsto 2^{\,d\cdot f(n)}$.

מה בדיוק צריך להוכיח. צריך להראות ש-$A$ שייכת לאיחוד, כלומר: מספיק להראות שקיים $d\ge 1$ שעבורו $A\in\mathrm{DTime}(2^{d\cdot f})$. זהו הפרמטר הנוסף שנכנס להוכחה, ולכן צריך להיות כאן זהירים יותר מבמשפט 2.

הוכחה. תהא $f:\mathbb{N}\to\mathbb{N}$. תהא $A\in\mathrm{DSpace}(f)$.

מהגדרת $\mathrm{DSpace}(f)$: קיימת מכונה $M$ וקיים $c>0$ כך ש-$M$ מכריעה את $A$, וגם לכל $x$: $\mathrm{space}_M(x)\le c\cdot f(|x|).$

מדוע פרסנו כאן את ההגדרה? כי היא מבטיחה קיום — היא נותנת לנו ליד את $M$ ואת $c$, ומהם (ורק מהם) נבנה את הפרמטרים החדשים ([00:23:49]).

נסמן ב-$Q,\Gamma$ את קבוצת המצבים ואלפבית הסרט של $M$, ונגדיר: $d=\max\Big\{\,1,\ \big(\lg|Q|+\lg|\Gamma|+1\big)\cdot c\,\Big\},\qquad \hat c=1 .$

אכן $d\ge 1$ כנדרש. נתבונן ב-$M$ (אותה מכונה) וב-$\hat c=1>0$. אכן $M$ מכריעה את $A$.

יהי $x$. מכיוון ש-$M$ מכריעה את $A$, בפרט $M$ עוצרת על $x$ — וזה בדיוק התנאי הדרוש כדי להפעיל את משפט 1 חלק ב'. לכן: $\mathrm{time}_M(x)\ \le\ 2^{(\lg|Q|+\lg|\Gamma|+1)\cdot \mathrm{space}_M(x)} \ \le\ 2^{(\lg|Q|+\lg|\Gamma|+1)\cdot c\cdot f(|x|)}\ \le\ 2^{\,d\cdot f(|x|)}\ =\ \hat c\cdot 2^{\,d\cdot f(|x|)} .$

האי-שוויון האמצעי מותר כי הפונקציה $t\mapsto 2^{\alpha t}$ עולה ב-$t$ עבור $\alpha>0$, והצבנו את החסם $\mathrm{space}_M(x)\le c\cdot f(|x|)$. האי-שוויון האחרון נובע מכך ש-$d\ge(\lg|Q|+\lg|\Gamma|+1)\cdot c$.

לכן $A\in\mathrm{DTime}(2^{d\cdot f})$, ומכאן $A\in\bigcup_{d\ge 1}\mathrm{DTime}(2^{d\cdot f})$. $\square$

חשבון הפרמטרים — למה $\hat c=1$ ולמה $d$ הוא זה. אחרי הצבת החסם על $\mathrm{space}$, האגף הימני הוא בדיוק מהצורה $2^{\,e\cdot f(|x|)}$ עבור מעריך $e$ כלשהו, בלי שום מקדם כפלי לפניו. הקבוע $\hat c$ הוא, לפי ההגדרה, המקדם שכופל את $2^{d\cdot f(|x|)}$ — ומכיוון שאין שם מקדם, $\hat c=1$ ([00:32:05]). ו-$d$ הוא כל מה שמוכפל ב-$f$ בתוך המעריך ([00:33:09]).

בדיקת שפיות (sanity check) שהמרצה הדגיש ([00:33:39]): ברגע שקובעים $d$, כל מה שנכנס לביטוי — $|Q|$, $|\Gamma|$, $c$ — כבר "ביד" מהשלב הקודם. אילו היינו נדרשים ל-$x$ או לגודל שתלוי בקלט, ההוכחה הייתה נופלת, כי $d$ נבחר לפני ה-$\forall x$.

הערה: הסיכום כותב $d=(\lg|Q|+\lg|\Gamma|+1)\cdot c$ ללא ה-$\max$. זה כמעט תמיד תקין, אבל אינו מובטח: הדרישה באיחוד היא $d\ge 1$, בעוד ההגדרה של $\mathrm{DSpace}$ מבטיחה רק $c>0$ — ואם למשל $c=0.1$ ו-$|Q|=|\Gamma|=2$ נקבל $d=0.3<1$. בשיעור עצמו סטודנט העלה בדיוק את הקושי הזה, והמרצה אישר שמותר "לתפור" את הקבוע כרצוננו ([00:24:21]–[00:24:53]). לקיחת $\max\{1,\cdot\}$ פותרת זאת ואינה פוגעת בחסם, כי הגדלת $d$ רק מגדילה את $2^{d\cdot f}$.

משפט 4: מונוטוניות ביחס לסדר גודל

תהיינה $f,g:\mathbb{N}\to\mathbb{N}$ ונניח $f=O(g)$. אז $\mathrm{DTime}(f)\subseteq\mathrm{DTime}(g)$

וגם

$\mathrm{DSpace}(f)\subseteq\mathrm{DSpace}(g).$

הוכחה (עבור $\mathrm{DTime}$; המקרה של $\mathrm{DSpace}$ זהה מילה במילה עם החלפת $\mathrm{time}$ ב-$\mathrm{space}$).

תהיינה $f,g$ ונניח $f=O(g)$. לפי הגדרה 3, קיים $c>0$ כך שלכל $n\in\mathbb{N}$: $f(n)\le c\cdot g(n).$

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

תהא $A\in\mathrm{DTime}(f)$. אז קיימת מכונה $M$ וקיים $\hat c>0$ כך ש-$M$ מכריעה את $A$ וגם לכל $x$: $\mathrm{time}_M(x)\le \hat c\cdot f(|x|).$

נתבונן ב-$M$ (אין מאיפה להביא מכונה אחרת) ונגדיר $\breve c=\hat c\cdot c .$

אכן $\breve c>0$ כמכפלת שני מספרים חיוביים, ואכן $M$ מכריעה את $A$. יהי $x$; אז $\mathrm{time}_M(x)\ \le\ \hat c\cdot f(|x|)\ \le\ \hat c\cdot c\cdot g(|x|)\ =\ \breve c\cdot g(|x|).$

לכן $A\in\mathrm{DTime}(g)$, ומכאן $\mathrm{DTime}(f)\subseteq\mathrm{DTime}(g)$. $\square$

שאלה טובה שנשאלה ([00:10:01] בהקלטה השנייה): "האם $\breve c=\hat c\cdot c$ באמת חיובי? אם שניהם קטנים מ-1, המכפלה קטנה משניהם." התשובה: המכפלה אכן עשויה להיות קטנה משני הגורמים, אבל זה לא משנה — ההגדרה דורשת רק $\breve c>0$, לא $\breve c\ge 1$ ולא $\breve c\ge\max$. ומעבר לכך, שרשרת האי-שוויונות למעלה מוכיחה את החסם ישירות, ללא כל הנחה על גודל הקבועים.

למה המשפט הזה חשוב. בלעדיו הכתיב $\mathrm{DTime}(n^2)$ היה שרירותי: הוא מבטיח שהמחלקות "מכבדות" סדרי גודל, ולכן הבחירה בין $f(n)=n^2$ ל-$f(n)=3n^2+5$ אינה משנה את המחלקה. הוא גם הכלי המרכזי בהוכחת $\mathrm{PSPACE}\subseteq \mathrm{EXP}$ (משפט 6).

משפט 5: $P\subseteq \mathrm{PSPACE}$

הוכחה א' (הוכחה "ארוכה", כפי שנעשתה בשיעור). תהא $A\in P$.

מהגדרת $P$ כאיחוד: קיים $c\ge 1$ כך ש-$A\in\mathrm{DTime}(n^c)$. (אי אפשר לקפוץ ישר למכונה — $P$ אינה מוגדרת על ידי מכונות אלא כאיחוד, ולכן קודם מקלפים את ה-"קיים $c$", [01:09:40].)

מהגדרת $\mathrm{DTime}(n^c)$: קיימת מכונה $M$ וקיים $d>0$ כך ש-$M$ מכריעה את $A$ וגם לכל $x$: $\mathrm{time}_M(x)\ \le\ d\cdot |x|^{c}.$

שימו לב להצבה: הפונקציה כאן היא $n\mapsto n^c$, והמשתנה שאנחנו עובדים איתו הוא $|x|$ — ולכן $d\cdot|x|^c$ ולא "$d\cdot n^c$" ([01:11:26]).

כדי להוכיח $A\in \mathrm{PSPACE}$ צריך להראות שקיים $\alpha\ge 1$ עם $A\in\mathrm{DSpace}(n^\alpha)$. נתבונן ב-$\alpha=c$ (הפרמטר היחיד שיש לנו ביד), ואז צריך להראות $A\in\mathrm{DSpace}(n^c)$:

• נתבונן ב-$M$ וב-$d$; אכן $d>0$ ואכן $M$ מכריעה את $A$.
• יהי $x$. לפי משפט 1 חלק א': $\mathrm{space}_M(x)\ \le\ \mathrm{time}_M(x)\ \le\ d\cdot|x|^{c}.$

לכן $A\in\mathrm{DSpace}(n^c)$, ולכן $A\in \mathrm{PSPACE}$. $\square$

הוכחה ב' (הפתרון האלטרנטיבי, עמוד 4 בסיכום). תהא $A\in P$. אז קיים $c\ge 1$ כך ש-$A\in\mathrm{DTime}(n^c)$. לפי משפט 2 (עם $f(n)=n^c$), $\mathrm{DTime}(n^c)\subseteq\mathrm{DSpace}(n^c)$, ולכן $A\in\mathrm{DSpace}(n^c)$ ומכאן $A\in \mathrm{PSPACE}$. $\square$

הערה: שתי ההוכחות תקפות לחלוטין, והשנייה קצרה בהרבה. המרצה הסביר במפורש ([01:16:21], [01:17:26]) שהוא פתח דווקא בארוכה מטעם דידקטי: היכולת לפרק הגדרה, להוציא את כל הפרמטרים, להשתמש בהם ולהרכיב אותם בחזרה היא המיומנות שכל ההוכחות הכבדות בקורס עומדות עליה. בבחינה — שתיהן מתקבלות.

משפט 6: $\mathrm{PSPACE}\subseteq \mathrm{EXP}$

(מופיע בהקלטה השנייה בלבד, [00:17:29]–[00:33:08]; אינו בסיכום.)

אינטואיציה. אם היחס בין מקום לזמן הוא אקספוננציאלי (משפט 1 חלק ב'), אז מי שנפתר במקום פולינומי חייב להיפתר בזמן אקספוננציאלי. אבל בין האינטואיציה הזו לבין ההגדרה הפורמלית של $\mathrm{EXP}$ יש פער טכני אמיתי, וכל עניינה של ההוכחה הוא לגשר עליו.

הוכחה. תהא $A\in \mathrm{PSPACE}$. אז קיים $c\ge 1$ כך ש-$A\in\mathrm{DSpace}(n^c)$, ולכן קיימת מכונה $M$ וקיים $c'>0$ כך ש-$M$ מכריעה את $A$ וגם לכל $x$: $\mathrm{space}_M(x)\le c'\cdot|x|^{c}.$

$M$ מכריעה את $A$, ולכן עוצרת על כל קלט. לפי משפט 1 חלק ב' קיים $c''>0$ (התלוי רק ב-$M$) כך שלכל $x$: $\mathrm{time}_M(x)\ \le\ 2^{\,c''\cdot \mathrm{space}_M(x)}\ \le\ 2^{\,c''\cdot c'\cdot |x|^{c}} .$

עד כאן קיבלנו $A\in\mathrm{DTime}\!\left(2^{\,c''c'\cdot n^{c}}\right)$ — וזו עדיין לא הגדרת $\mathrm{EXP}$, שדורשת מחלקה מהצורה $\mathrm{DTime}(2^{n^{k}})$ בדיוק, בלי קבועים בתוך המעריך.

נסמן $g(n)=2^{\,c''c'\cdot n^{c}},\qquad h(n)=2^{\,n^{c+1}} .$

נטען ש-$g=O(h)$. אכן, לכל $n\ge n_0:=c''c'$ מתקיים $c''c'\cdot n^{c}\le n\cdot n^{c}=n^{c+1}$, ומכיוון ש-$2^{t}$ עולה ב-$t$ נקבל $g(n)\le h(n)$ לכל $n\ge n_0$. לפי הגדרת $O$ (ובעזרת השקילות מהגדרה 3, שמאפשרת לוותר על $n_0$ במחיר קבוע), $g=O(h)$.

לפי משפט 4, $\mathrm{DTime}(g)\subseteq\mathrm{DTime}(h)$, ולכן $A\in\mathrm{DTime}\!\left(2^{\,n^{c+1}}\right)\subseteq \mathrm{EXP}. \qquad\square$

למה זו הדרך הנכונה. אפשר, לחלוטין, לרדוף אחרי הקבוע ולמצוא במפורש $D$ ו-$D'$ כך ש-$\mathrm{time}_M(x)\le D\cdot 2^{|x|^{D'}}$ לכל $x$ — וזה אפילו לא קשה (ראו התרגיל בסעיף הבא). אבל זו עבודה טכנית מיותרת: מכיוון שבסופו של דבר אנחנו מסתכלים על סדרי גודל, נכון יותר לשאול מה קורה כשהקלט הולך וגדל, לזהות שמאורך מסוים כל הקבועים "נבלעים" בתוך $n$, ואז לקבל את המעבר מ-$n_0$ ל"לכל $n$" בחינם משקילות הגדרות ה-$O$ ([00:28:19]–[00:34:41]).

דוגמאות ותרגילים מהשיעור

דוגמה 1: $PAL\in\mathrm{DTime}(n^2)$, מפורק עד הסוף

$PAL=\{x\in\{0,1\}^*\mid x=x^R\}$ — שפת הפלינדרומים מעל $\{0,1\}$.

האלגוריתם (על מכונה חד-סרטית סטנדרטית): כל עוד נשארו לפחות שני תווים — קרא את התו השמאלי ביותר שלא נמחק, מחק אותו, סע ימינה עד התו הימני ביותר שלא נמחק, השווה, ומחק גם אותו; חזור שמאלה. אם בכל השוואה היה שוויון — קבל; אם הייתה אי-התאמה — דחה.

חשבון הזמן. בסבב מספר $i$ (כאשר $i=1,2,\dots$) נותרו $n-2(i-1)$ תווים, והמכונה עוברת את המרווח הזה הלוך ושוב — כלומר כ-$2\big(n-2(i-1)\big)$ צעדים. סכימה על כל הסבבים, $i=1,\dots,\lceil n/2\rceil$: $\mathrm{time}_M(x)\ \approx\ \sum_{i=1}^{\lceil n/2\rceil} 2\big(n-2(i-1)\big)\ \le\ 2\cdot \frac{n}{2}\cdot n\ =\ n^2 .$

אם ניקח $f(n)=n^2$ ו-$c=2$ (כדי לבלוע בנדיבות את צעדי הבקרה), נקבל $\mathrm{time}_M(x)\le c\cdot f(|x|)$ לכל $x$, ולכן $PAL\in\mathrm{DTime}(f)$.

מופע קונקרטי — $x=0110$ ($n=4$): סבב 1 משווה את התו הראשון $0$ לתו האחרון $0$ — התאמה, שניהם נמחקים; נותר $11$. סבב 2 משווה $1$ ל-$1$ — התאמה. לא נותרו תווים ⟸ קבל. סה"כ כ-$8+4=12\le 2\cdot 4^2$ צעדים.

אי-מופע — $x=0100$: סבב 1 משווה $0$ ל-$0$ — התאמה; נותר $10$. סבב 2 משווה $1$ ל-$0$ — אי-התאמה ⟸ דחה.

על הסימון. פורמלית היינו צריכים לכתוב: "תהא $f:\mathbb{N}\to\mathbb{N}$ המוגדרת על ידי $f(n)=n^2$ לכל $n\in\mathbb{N}$; אז $PAL\in\mathrm{DTime}(f)$." מקובל לקצר ולכתוב פשוט $PAL\in\mathrm{DTime}(n^2)$. שימו לב ש-$n^2$ הוא מספר, לא פונקציה — הכתיב הזה הוא קיצור שממנו מובן לאיזו פונקציה התכוונו ([00:45:24]).

אזהרה מהשיעור ([00:43:17]): אל תסיקו מכאן ש"פלינדרומים זה $n$" מתוך זיכרון של קורס אחר. החסם הריבועי נובע מכך שהמודל הוא חד-סרטי. במודל אחר (למשל שני סרטים) המספר משתנה.

תרגיל 1 (נשאל בכיתה, [00:15:49])

אם מספר הצעדים שהמכונה מבצעת נשאר בדיוק אותו דבר, אבל הקלט נעשה ארוך יותר — האם הסיבוכיות גדלה או קטנה?

פתרון. קטנה. סיבוכיות נמדדת ביחס לאורך הקלט: אם $\mathrm{time}_M(x)$ קבוע ו-$|x|$ גדל, אז היחס $\mathrm{time}_M(x)/f(|x|)$ קטן, והחסם $c\cdot f(|x|)$ הופך נדיב יותר. האינטואיציה שהוצעה בשיעור: חִשבו על זמן ומקום כעל מחיר ועל הקלט כעל מה שקיבלתם תמורתו — שילמתם אותו מחיר וקיבלתם קלט גדול יותר, כלומר עשיתם עסקה טובה יותר.

תרגיל 2 (עלה כשאלה, [00:14:08])

למה כתוב $f(|x|)$ ולא $f(x)$?

פתרון. $f$ מוגדרת מ-$\mathbb{N}$ ל-$\mathbb{N}$, ו-$x$ הוא מחרוזת מעל אלפבית כלשהו. $f(x)$ הוא ביטוי חסר משמעות — אין ל-$f$ הגדרה על מחרוזות. $|x|$ הוא אורך המחרוזת, שהוא מספר טבעי, ולכן $f(|x|)$ מוגדר היטב. הערכים המוחלטים כאן אינם קידוד ואינם ייצוג — הם פשוט אורך.

תרגיל 3: מציאת הקבוע במפורש ב-$\mathrm{PSPACE}\subseteq \mathrm{EXP}$

במשפט 6 עקפנו את חיפוש הקבוע. מצאו אותו במפורש.

פתרון. נסמן $n_0=c''c'$. הראינו שלכל $x$ עם $|x|\ge n_0$ מתקיים $\mathrm{time}_M(x)\le 2^{|x|^{c+1}}$. נותרו קלטים באורך $<n_0$ — ויש מספר סופי של קלטים כאלה (האלפבית סופי). $M$ מכריעה את $A$, ולכן עוצרת על כל אחד מהם; נסמן ב-$T$ את המקסימום של $\mathrm{time}_M(x)$ על פני קבוצה סופית זו. ניקח $D=\max\{1,\ T\}.$ אז לכל $x$: אם $|x|\ge n_0$ אז $\mathrm{time}_M(x)\le 2^{|x|^{c+1}}\le D\cdot 2^{|x|^{c+1}}$, ואם $|x|<n_0$ אז $\mathrm{time}_M(x)\le T\le D\le D\cdot 2^{|x|^{c+1}}$. לכן $A\in\mathrm{DTime}(2^{n^{c+1}})$. זהו בדיוק המנגנון שמאחורי השקילות בהגדרה 3 — "בליעת" מספר סופי של קלטים חריגים בתוך הקבוע.

תרגיל 4: קריאת הקיצור $\mathrm{DTime}(2^{O(f)})$

מה הולך לאיבוד בכתיב המקוצר?

פתרון. לפעמים מקצרים $\bigcup_{d\ge1}\mathrm{DTime}(2^{d\cdot f})$ ל-$\mathrm{DTime}(2^{O(f)})$. מה שנעלם הוא הפרמטר $d$ והכמת שמעליו. שייכות לאיחוד היא טענת קיום, ובלי הפרמטר אין במה "לתפוס" את ההוכחה. הקיצור לגיטימי ואתם חייבים לדעת לקרוא אותו, אבל כשאתם באים להוכיח שייכות — פתחו אותו חזרה ל-"קיים $d\ge1$ כך ש..." ([00:47:29]–[00:49:02]).

תרגיל 5: $\mathrm{DTime}(n)\subseteq\mathrm{DTime}(n^2)$

פתרון. $f(n)=n$, $g(n)=n^2$. מתקיים $f(n)=n\le 1\cdot n^2=g(n)$ לכל $n\in\mathbb{N}$, ולכן $f=O(g)$ עם $c=1$ (בגרסה ללא $n_0$). לפי משפט 4, $\mathrm{DTime}(n)\subseteq\mathrm{DTime}(n^2)$. שימו לב שהמשפט אינו אומר דבר על הכלה ממש — השאלה אם ההכלה חזקה היא בדיוק נושא שיעור 3 (משפטי ההיררכיה).

הערות מהשיעור

• [00:01:08] החסם על מספר הקונפיגורציות אינו הדוק, וזה יחזור. "לפעמים אנחנו נרצה לחזור לכאן — עם ה-space מאוד גדול, יכול להיות שזה משמעותי." ואכן, בשיעור 3 חוזרים בדיוק לחישוב הזה וחוסמים אותו אחרת כדי לקבל קבוע שאינו תלוי במכונה.
• [00:01:40] סדר הכמתים. "תשימו לב לסדר הכמתים, זה מאוד מאוד חשוב." זו האזהרה החוזרת ביותר בשיעור, והיא הנקודה שקורסת בשיעור 3 כשהמכונה עצמה היא הקלט.
• [00:04:28] אינטואיציה מול פורמליזם. "בהגדרה האינטואיטיבית הייתי משתמש כשאני רוצה לחשוב על המחלקות, אבל לא כשאני צריך לשבת ולהוכיח משהו עליהן." כשמוכיחים — יורדים לפורמליזם, כי רק הוא נותן ליד את המכונה ואת הקבועים.
• [00:06:01] שאלת סטודנט: אוטומטים או מכונות טיורינג? מכונות טיורינג. לאוטומט הזמן ידוע מראש והוא ליניארי, ולכן אין בו עניין סיבוכיותי.
• [00:08:17] "אני לא מניח שיש איבר — אני לוקח איבר." תיקון ניסוח שהמרצה עמד עליו: בהוכחת הכלה $\forall A\in X:\ A\in Y$ אין הנחת קיום; לוקחים איבר שרירותי. הבלבול הזה הוא מקור נפוץ לשגיאות.
• [00:09:58] אל תתחילו מהסוף של ההגדרה. טעות נפוצה: מרגישים שכבר "כתבנו את ההתחלה" של ההגדרה בצד הנתון, ולכן קופצים ישר לאי-שוויון בצד שצריך להוכיח. בצד הנתון פרסנו את מה שנובע; בצד שצריך להוכיח צריך להוכיח את הכול מחדש.
• [00:17:26] מחלקה היא קבוצה שאיבריה שפות. $A$ אינה מכונת טיורינג.
• [00:23:49] מתי מצטטים הגדרה? "כשהיא מבטיחה לי קיום של משהו." אם ההגדרה מספקת מכונה או קבוע שאזדקק להם — פורסים אותה. אחרת, בדרך כלל לא.
• [00:33:39] בדיקת שפיות. כשקובעים קבוע חדש, ודאו שהוא מורכב רק מדברים שכבר יש ביד באותו שלב בהוכחה. שימוש במשתנה שעדיין לא הוצג הוא כמעט תמיד סימן לשגיאה מהותית.
• [00:41:06] מדוע "מחלקות עדינות". כי כל פונקציה $f$ מייצרת מחלקה משלה — התאמה חד-חד-ערכית בין פונקציות למחלקות.
• [00:49:33] על קיצורים. "כל זמן שזה תלוי בי אני לא אקצר — אבל אתם כן צריכים לדעת לקרוא את זה. מישהו אחר יקצר לכם."
• [01:00:30] עבדו בטיוטה. הקבועים ($d$, $\hat c$, $\breve c$) נמצאים בטיוטה, ולהוכחה מגיעים כשכבר יודעים מה הם. אל תנסו לכתוב הוכחה כזו ב-one pass.
• [01:19:36] מה הלאה. "שיעור הבא נגיע למשפט ההיררכיה, ואז תראו מה זו הוכחה מורכבת. קחו אוויר."
• [01:20:38] על שינון. ההמלצה: לא לשנן הגדרות. לכתוב את ההגדרה על פתק, לתלות אותה מול העיניים, ולפתור מספיק תרגילים עד שהיא נכנסת דרך שימוש. עד כשלושה ימים לפני המבחן — לעבוד עם החומר פתוח.
• [00:14:47] בהקלטה השנייה: $P$ כ"קל" ומחוץ ל-$P$ כ"קשה". מקובל לזהות את $P$ עם הבעיות הפתירות ביעילות. כל מה שנפגשתם בו בקורסי אלגוריתמים היה בתוך $P$.
• [00:15:53] בהקלטה השנייה: הפער בתוך $P$ עצמה. יש תהום בין $\mathrm{DTime}(n)$ ל-$\mathrm{DTime}(n^{100})$ — האחרון אינו ישים בפועל, ועדיין הוא ב-$P$. ההצדקה האמפירית לזיהוי $P$="יעיל": כשמצליחים לפתור בעיה בזמן פולינומי כלשהו, בדרך כלל מוצאים אחר כך גם פולינום קטן.
• [00:16:57] בהקלטה השנייה: גם קושי הוא מוצר. שיטת ההצפנה RSA נשענת על ההשערה שפירוק לגורמים ראשוניים אינו ניתן לפתרון בזמן פולינומי. לא יודעים להוכיח זאת, אך מסתמכים על כך.

פערים בין הסיכום להקלטה

• מקור: עמוד 1 בסיכום. הפער: הסיכום נפתח באמצע ניסוח המשפט על הקשר בין זמן למקום ואינו כולל את הוכחתו (היא נעשתה בשיעור 1); ההקלטה מזכירה אותה בשלוש שורות בלבד. ההכרעה: שחזרתי את הספירה המלאה של הקונפיגורציות כמשפט 1, כולל הצדקת כל אחד משלושת המעברים שמייצרים את $c=\lg|Q|+\lg|\Gamma|+1$, בהסתמך על החישוב שנעשה במפורש בהקלטה השנייה ב-[01:13:37]–[01:15:14].
• מקור: עמוד 2 בסיכום, הוכחת משפט 3. הפער: הסיכום קובע $d=(\lg|Q|+\lg|\Gamma|+1)\cdot c$, אך האיחוד הוא על $d\ge 1$ בעוד ההגדרה מבטיחה רק $c>0$ — ולכן ייתכן $d<1$ (למשל $c=0.1$, $|Q|=|\Gamma|=2$). ההכרעה: תיקנתי בגוף ל-$d=\max\{1,(\lg|Q|+\lg|\Gamma|+1)\cdot c\}$. התיקון אינו פוגע בחסם כי $2^{d\cdot f}$ מונוטונית עולה ב-$d$. הקושי הזה הועלה בפועל על ידי סטודנט בהקלטה ב-[00:24:21] והמרצה אישר את עקרון "התפירה" של הקבוע.
• מקור: ההקלטה השנייה, [00:17:29]–[00:33:08]. הפער: המשפט $\mathrm{PSPACE}\subseteq \mathrm{EXP}$ נלמד ולא מופיע בסיכום כלל. ההכרעה: הוספתי אותו כמשפט 6, כולל שתי הדרכים (חיפוש הקבוע מול הטיעון האסימפטוטי), כי הוא ההשלמה הטבעית ל-$P\subseteq \mathrm{PSPACE}$ ומדגים את השימוש במשפט 4.
• מקור: עמוד 3 בסיכום, ההערה האדומה על הגדרת $O$. הפער: כיוון אי-השוויון בכתב היד ניתן לקריאה כ-$\ge$. ההכרעה: ההגדרה הנכונה של $f=O(g)$ היא $f(n)\le c\cdot g(n)$, וכך גם נאמר במפורש בשתי ההקלטות ([00:52:32] ו-[00:04:10] בהקלטה השנייה). כתבתי $\le$.
• מקור: עמוד 2 בסיכום, שורת ה-PAL. הפער: נראה שכתוב "$PAL=\mathrm{DTime}(f)$" במקום "$PAL\in\mathrm{DTime}(f)$". ההכרעה: מדובר בשפה בודדת מול מחלקה של שפות, ולכן היחס הוא שייכות; כתבתי $\in$. ההקלטה ([00:44:23]) אומרת "פל ב-DTime f", כלומר שייכות.
• מקור: עמוד 3 בסיכום. הפער: המחלקה נכתבת "$EX$". ההכרעה: הכוונה ל-$\mathrm{EXP}$ (בהקלטה: "אקספ"); כתבתי $\mathrm{EXP}$. באותו אופן, הסיכום כותב $EXSPACE$ ואני כתבתי $\mathrm{EXPSPACE}$ — אותו אובייקט.
• מקור: שני המקורות. הפער: נושא חוסן המודל (מדוע בחירת מודל המכונה אינה משנה את $P$) אינו נדון בשיעור הזה כלל. ההתייחסות היחידה למודל היא ההסכמה שב-[00:43:50] ש"מכונה" פירושה חד-סרטית סטנדרטית, ואזהרה שחסמים קונקרטיים כמו $n^2$ עבור $PAL$ כן תלויים במודל. ההכרעה: לא הוספתי דיון בחוסן המודל כדי לא להמציא חומר; ציינתי את הסכמת המודל ואת תלות החסם בו.
• מקור: ההקלטה השנייה (video_id ilc7hKBsa1Q). הפער: מדקה 36 ואילך ההקלטה עוברת למשפט היררכיית המקום — הגדרת "ישימה במקום", השפה $S_f$, טענת העזר על $2^{3f(\langle M\rangle)}$ צעדים — שהוא כולו חומר של שיעור 3. ההכרעה: סימנתי coverage: partial והשארתי את החומר הזה מחוץ לקובץ.
• מקור: עמוד 1 בסיכום. הפער: הקיצור שליד "לכל מכונה $M$" אינו קריא בבירור. ההכרעה: מההקשר ומההקלטה ([00:01:40] "לכל מכונה") ברור שהכוונה למכונת טיורינג דטרמיניסטית; כתבתי כך.

סיכום ונקודות למבחן

מה חייבים לדעת בעל פה (או, לפי המלצת המרצה, מתוך שימוש חוזר):

1. $A\in\mathrm{DTime}(f)$ $\iff$ $\exists M\ \exists c>0$: $M$ מכריעה את $A$ וגם $\forall x:\ \mathrm{time}_M(x)\le c\cdot f(|x|)$. אותו הדבר ל-$\mathrm{DSpace}$.
2. $\mathrm{space}_M(x)\le \mathrm{time}_M(x)$ — תמיד, ללא הנחות.
3. אם $M$ עוצרת על $x$: $\mathrm{time}_M(x)\le 2^{c\cdot\mathrm{space}_M(x)}$ עם $c=\lg|Q|+\lg|\Gamma|+1$ התלוי רק במכונה.
4. $\mathrm{DTime}(f)\subseteq\mathrm{DSpace}(f)$; $\ \mathrm{DSpace}(f)\subseteq\bigcup_{d\ge1}\mathrm{DTime}(2^{d\cdot f})$.
5. $f=O(g)\ \Rightarrow\ \mathrm{DTime}(f)\subseteq\mathrm{DTime}(g)$ ו-$\mathrm{DSpace}(f)\subseteq\mathrm{DSpace}(g)$.
6. $P\subseteq \mathrm{PSPACE}\subseteq \mathrm{EXP}$.

המלכודות הסטנדרטיות:

• שכחת הנחת העצירה. כל שימוש בחסם $2^{c\cdot\mathrm{space}}$ מחייב הצדקה מפורשת ש-$M$ עוצרת על הקלט הנדון. בהוכחות שלנו זה תמיד מגיע מ"$M$ מכריעה את $A$, ולכן עוצרת על כל קלט". בלי ההנחה הזו הטענה שקרית — הזמן אינו חסום על ידי שום פונקציה של המקום.
• קפיצה מעל האיחוד. כשמוכיחים שייכות ל-$P$/$\mathrm{PSPACE}$/$\mathrm{EXP}$ — קודם "קיים $c\ge1$", ורק אחר כך "קיימת מכונה". אי אפשר לגשת ישר למכונה, כי המחלקה הגסה אינה מוגדרת דרך מכונות.
• בלבול $f(x)$ עם $f(|x|)$.
• קבוע שנבנה ממשתנה שעדיין לא קיים. כל קבוע חדש חייב להיות מורכב מפרמטרים שכבר "הוצאו" מהגדרות קודמות, ולהיקבע לפני ה-$\forall x$.
• התעלמות מ-$d\ge 1$ / $c\ge 1$ בהגדרות האיחודים. כשהקבוע שהתקבל קטן מ-1 — קחו $\max$.
• הנחה ש"פלינדרומים זה ליניארי". לא במודל החד-סרטי.

צ'קליסט — אחרי השיעור הזה אתם אמורים לדעת:

• לכתוב מזיכרון את הגדרות $\mathrm{DTime}(f)$ ו-$\mathrm{DSpace}(f)$ עם סדר הכמתים הנכון.
• להוכיח שייכות של שפה נתונה למחלקה עדינה על ידי הצגת מכונה, קבוע, וחסם — בכל חמשת חלקי ההגדרה.
• להוכיח הכלה בין שתי מחלקות עדינות/גסות במבנה המלא: לקחת איבר, לפרוס את ההגדרה הנתונה, להגדיר את הפרמטרים החדשים מתוך הישנים, ולהרכיב את ההגדרה שצריך להוכיח.
• לחשב את מספר הקונפיגורציות של מכונה בריצה שהמקום שלה חסום, ולהסיק ממנו חסם זמן.
• לזהות מתי כדאי לרדוף אחרי קבוע מפורש ומתי עדיף לעבור לטיעון אסימפטוטי דרך משפט 4.
• לקרוא נכון קיצורים כמו $\mathrm{DTime}(2^{O(f)})$ ו-$\mathrm{DTime}(n^2)$, ולפתוח אותם חזרה לניסוח הפורמלי בעת הצורך.

הסיכום הכתוב הוא של גיא סופר.