3משפטי היררכיה במקום ובזמן

בקצרה

• זהו השיעור הראשון בקורס שבו מוכיחים תוצאה שלילית ברמת הסיבוכיות: לא רק ש"אפשר לעשות משהו בתקציב נתון", אלא שאי אפשר לעשות משהו בתקציב נתון. תוצאות כאלה קשות בהרבה מתוצאות חיוביות ולכן יש מעט מהן.
• משפט ההיררכיה במקום: אם $g=o(f)$, אם $f$ ישימה במקום (space-constructible) ואם $f$ סופר־לינארית, אז $\mathrm{DSpace}(g)\subsetneq\mathrm{DSpace}(f)$. כלומר תוספת משמעותית של מקום נותנת ממש יותר כוח חישובי.
• משפט ההיררכיה בזמן: באותם תנאים, אבל עם $f$ ישימה בזמן (time-constructible), מקבלים רק $\mathrm{DTime}(g)\subsetneq\mathrm{DTime}(f^2)$. הריבוע הזה אינו קישוט — הוא נובע נקודתית מהמעבר ממכונה רב־סרטית למכונה סטנדרטית, שבמקום עולה קבוע כפלי ובזמן עולה ריבוע.
• ההוכחה היא לכסון בסגנון חישוביות (השפה של המכונות שדוחות את הקידוד של עצמן), אבל עם רכיב סיבוכיותי שמפצל את עולם המכונות: מי שמשתמשת במעט מקום נופלת במלכודת הלכסון, ומי שמשתמשת בהרבה מקום בורחת ממנה.
• שני התנאים הטכניים אינם קישוט: הישימות דרושה כדי שהמכונה שבונים תוכל בכלל לכתוב את המונים בתוך התקציב, והסופר־לינאריות דרושה כדי לבלוע את $|\langle M\rangle|$ ואת $\lg f$ בתוך $f$ בחשבון הזמן והמקום.
• מסקנה מרכזית: $\mathrm P\subsetneq\mathrm{EXP}$. ומכיוון ש-$\mathrm P\subseteq\mathrm{PSPACE}\subseteq\mathrm{EXP}$, לפחות אחת משתי ההכלות האלה היא הכלה ממש — ואף אחד לא יודע איזו. שתי השאלות פתוחות זה עשרות שנים.
• מלכודת שחוזרת: הכלה נשמרת תחת איחוד, הכלה ממש לא. לכן אי אפשר להפעיל את משפט ההיררכיה ישירות על מחלקות גסות כמו $\mathrm P$ ו-$\mathrm{EXP}$; חייבים לעבור דרך שתי מחלקות עדינות באמצע.

רקע ותלויות

השיעור הזה נשען כמעט על כל מה שנבנה עד כה, ולכן נחזור על התוצאות שנשתמש בהן ממש, בניסוח מלא.

מהשיעורים 1–2: המחלקות

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

מהשיעור 2: מונוטוניות במשאב

טענה. לכל $f,g:\mathbb N\to\mathbb N$: אם $g=O(f)$ אז $\mathrm{DTime}(g)\subseteq\mathrm{DTime}(f)$ וגם $\mathrm{DSpace}(g)\subseteq\mathrm{DSpace}(f)$.

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

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

מהשיעור 2: מקום חוסם זמן

טענה. $\mathrm{DSpace}(f)\subseteq\bigcup_{d\ge 1}\mathrm{DTime}\!\left(2^{d\cdot f}\right)$.

ההוכחה שלה נשענה על ספירת קונפיגורציות, והשורה שנצטרך כאן היא לא התוצאה הסופית אלא השורה שלפניה: אם $M$ עוצרת על קלט $x$ אז

הביטוי הזה הוא בדיוק מספר הקונפיגורציות האפשריות: $|Q_M|$ בחירות של מצב, $|\Gamma_M|^{\mathrm{space}_M(x)}$ תוכני סרט, ו-$\mathrm{space}_M(x)$ מיקומי ראש. אם המכונה עושה יותר צעדים מזה — קונפיגורציה חוזרת על עצמה והמכונה לעולם לא תעצור.

מהשיעור 1: המכונה האוניברסלית והמעבר בין מודלים

שני מדדים של המכונה האוניברסלית $M_U$ על קלט $\langle M,x\rangle$ יופיעו כאן במפורש:

ההסבר לפקטור $\lg|\Gamma_M|$: האוניברסלית עובדת מעל קידוד בינרי, ולכן כל תא של $M$ עולה לה $\lg|\Gamma_M|$ תאים. שימו לב להבדל בין שני המדדים — במקום משלמים $\lg|\Gamma_M|$, בזמן משלמים $|\langle M\rangle|$. כל ההבדל בין שני משפטי ההיררכיה יצמח מהנקודה הזאת.

וכן, ההמרה בין מודלים:

טענה. לכל מכונה רב־סרטית $M$ קיימת מכונה סטנדרטית (חד־סרטית) $\hat M$ השקולה לה סמנטית, כך ש-$\mathrm{space}_{\hat M}(x)=O(\mathrm{space}_M(x))$ אבל $\mathrm{time}_{\hat M}(x)=O\!\left(\mathrm{time}_M(x)^2\right)$.

זו הנקודה — ורק היא — שמכניסה את הריבוע למשפט ההיררכיה בזמן.

הגדרות

הגדרה 1: ישימות במקום (space-constructible)

תהי $f:\mathbb N\to\mathbb N$. נאמר ש-$f$ ישימה במקום אם קיימת מכונת טיורינג $M$ מעל אלפבית קלט $\{0\}$ (אלפבית של אות אחת) המקיימת, לכל $n\in\mathbb N$:

1. $M(0^n)=0^{f(n)}$;
2. $\mathrm{space}_M(0^n)=O(f(n))$.

אינטואיציה. התנאי הראשון לבדו אומר רק ש-$f$ חשיבה: נותנים למכונה את המספר $n$ (מקודד באונרית — אורך המחרוזת הוא המספר) והיא מחזירה את $f(n)$ באותו קידוד. התנאי השני מוסיף את הדרישה הסיבוכיותית: המקום שדרוש כדי לחשב את $f$ אינו גדול משמעותית מגודל הפלט עצמו. אפשר לקרוא את זה כך — אפשר לבנות את $f$ בתוך המקום של עצמה. שימו לב ש-$O(\cdot)$ ולא שוויון: מותר לצרוך קצת יותר מקום מהפלט, עד כדי קבוע כפלי.

הערה על סימונים: בכתב יד קל להתבלבל בין הספרה $0$ בתוך $0^n$ לבין הסימון $O(\cdot)$. שאלת סטודנט בהקלטה [00:22:10] הייתה בדיוק זו — ב-$M(0^n)$ מדובר בספרה אפס, כלומר מחרוזת של אפסים; אין משמעות ל"$O$ בחזקת $n$".

מופע. $f(n)=n^2$ ישימה במקום: קל לבנות מכונה שכותבת $n^2$ אפסים תוך שימוש ב-$O(n^2)$ תאים.

אי־מופע (הבהרת הגבול). פונקציה שאינה חשיבה כלל — למשל $f(n)=$ מספר המכונות בגודל $n$ שעוצרות על הקלט הריק — בוודאות אינה ישימה במקום, כי אפילו התנאי הראשון נכשל. בקורס הזה כמעט לא ניתקל בכאלה: אנחנו כבר לא בעולם של $\mathbb R$ ולא בעולם של פונקציות לא חשיבות.

הגדרה 2: ישימות בזמן (time-constructible)

באופן דומה לחלוטין, רק שהתנאי השני מוחלף ב-$\mathrm{time}_M(0^n)=O(f(n))$.

משפט עזר (ללא הוכחה, מותר להשתמש)

כל הפונקציות האלמנטריות — פולינומים, אקספוננטים, לוגריתמים והרכבות שלהן — ישימות במקום וישימות בזמן.

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

הגדרה 3: סופר־לינאריות

$f$ נקראת סופר־לינארית אם $f(n)\ge n$ לכל $n\in\mathbb N$.

אינטואיציה. זו הדרישה שהתקציב יספיק לפחות כדי לקרוא את הקלט. היא תשמש אותנו פעמיים בחשבון, שתיהן בצורה "בלע את $|\langle M\rangle|$ בתוך $f(|\langle M\rangle|)$".

הגדרה 4: השפה $S_f$ — האלכסון

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

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

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

מאיפה התנאי הראשון. אם משמיטים לגמרי את תנאי המקום, נשארים עם השפה $\{\langle M\rangle\mid M \text{ rejects } \langle M\rangle\}$. זו בדיוק שפת הלכסון מחישוביות, והיא אינה כריעה: אילו הייתה מכונה $M'$ שמכריעה אותה, נשאל מה היא מחזירה על $\langle M'\rangle$. אם היא מקבלת — אז $\langle M'\rangle\in$ השפה, אבל השייכות דורשת שהיא תדחה, סתירה. אם היא דוחה — אז לפי ההגדרה $\langle M'\rangle$ כן בשפה, ולכן היא הייתה צריכה לקבל, סתירה. יש קלט אחד — הקידוד של עצמה — שעליו כל מכונה טועה.

מה עושה התנאי השני. תנאי המקום מפצל את עולם המכונות לשניים:

• מכונה שמשתמשת ב-$O(g)$ מקום: מכיוון ש-$g$ קטנה בסדר גודל מ-$f$, תנאי המקום מתקיים אצלה אוטומטית (עבור קידודים ארוכים מספיק). ולכן היא נשארת לכודה בדיוק באותה סתירה — היא לא יכולה להכריע את $S_f$.
• מכונה שמשתמשת ביותר מ-$f(|\langle M\rangle|)/\lg|\Gamma_M|$ מקום: אצלה תנאי המקום נכשל, ולכן היא יכולה לדחות את הקידוד של עצמה בלי להיכנס לסתירה — היא פשוט אינה שייכת ל-$S_f$, ולא בגלל תנאי הלכסון אלא בגלל תנאי המקום. מכונות כאלה הן היחידות שיש להן סיכוי להכריע את $S_f$.

זו התשובה לשאלה המתבקשת ששאל סטודנט [00:09:30]: "אם השפה הזו לא כריעה, איך היא בכלל יכולה להיות ב-$\mathrm{DSpace}(f)$?" — התשובה היא שהיא כן כריעה; תנאי המקום הוא שהופך אותה לכריעה, ולא סתם כריעה, אלא כריעה בדיוק על ידי מכונות שמעל הסף.

מאיפה החלוקה ב-$\lg|\Gamma_M|$. זהו הפרט הסיבוכיותי היחיד בהגדרה. כשנכריע את $S_f$ נריץ מכונה אוניברסלית, והמקום שהיא דורשת הוא $O(\mathrm{space}_M(x)\cdot\lg|\Gamma_M|)$. אם נחסום את $\mathrm{space}_M$ ב-$f/\lg|\Gamma_M|$, אז ה-$\lg|\Gamma_M|$ מצטמצם ונשארים עם $O(f)$ — חסם שאינו תלוי במכונה שמריצים. בלי החלוקה הזו היה נשאר קבוע שתלוי בקלט, ומחלקת $\mathrm{DSpace}$ אינה סובלת קבוע כזה. אותו צמצום בדיוק יקרה גם בחשבון הזמן, כי גם שם הפקטור הדומיננטי הוא $2^{\lg|\Gamma_M|\cdot \mathrm{space}_M}$.

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

משפט 1 (חימום): $\mathrm{PSPACE}\subseteq\mathrm{EXP}$

הוכחה. תהי $A\in\mathrm{PSPACE}$.

1. לפי הגדרת $\mathrm{PSPACE}$ כאיחוד, קיים $c\ge 1$ כך ש-$A\in\mathrm{DSpace}(n^c)$. (הצעד הראשון תמיד: לקלף את האיחוד החוצה.)
2. מהטענה שהוכחנו בשיעור 2, $\mathrm{DSpace}(f)\subseteq\bigcup_{d\ge1}\mathrm{DTime}(2^{d\cdot f})$, ולכן $A\in\bigcup_{d\ge 1}\mathrm{DTime}\!\left(2^{d\cdot n^c}\right)$.
3. שוב מקלפים את האיחוד: קיים $d\ge 1$ כך ש-$A\in\mathrm{DTime}\!\left(2^{d\cdot n^c}\right)$.
4. וכאן נתקעים לרגע — הצורה $2^{d\cdot n^c}$ אינה מהצורה $2^{n^{c'}}$ שממנה בנויה $\mathrm{EXP}$.

הנקודה שהמרצה עצר עליה: קבוע כפלי בתוך החזקה אינו זניח. קבוע כפלי מחוץ לפונקציה תמיד נבלע ב-$O(\cdot)$ ובקבוע של המחלקה, אבל $2^{2n}$ ו-$2^{n}$ אינם מאותו סדר גודל בכלל — היחס ביניהם הוא $2^n$. אי אפשר "להעיף" את $d$.

מה כן אפשר? להשתמש בכך ש-$\mathrm{EXP}$ הוא איחוד על כל החזקות, ולכן מותר לנו לקחת חזקה גדולה יותר. לכל $n\ge d$ מתקיים $d\cdot n^c\le n\cdot n^c=n^{c+1}$, ולכן

5. לכן $A\in\mathrm{DTime}\!\left(2^{n^{c+1}}\right)\subseteq\mathrm{EXP}$. $\blacksquare$

למה בדיוק $c+1$? מפני ש-$d$ קבוע ו-$n$ לא. הגדלת החזקה של $n$ באחד מספיקה כדי לבלוע כל קבוע כפלי, עבור $n$ גדולים מספיק. אם נחזור לדוגמה: $2^{2n}$ גדול בהרבה מ-$2^{n}$, אבל קטן בהרבה מ-$2^{n^2}$. (גם $c\cdot d$ בחזקה היה עובד — הוא $\ge c$ כי $d\ge1$ — אבל $c+1$ פשוט יותר.)

משפט 2 (גרסת החלומות — לא נכון שיודעים להוכיח)

תהיינה $f,g:\mathbb N\to\mathbb N$. אם $g=o(f)$ אז $\mathrm{DSpace}(g)\subsetneq\mathrm{DSpace}(f)$.

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

שימו לב למה קופצים כאן מ-$O$ גדול ל-$o$ קטן: $O$ גדול נותן רק את התוצאה החיובית ($\mathrm{DSpace}(g)\subseteq\mathrm{DSpace}(f)$). $o$ קטן אומר שהתקציב גדל בסדר גודל, וזה מה שנדרש כדי לקוות לתוצאה שלילית.

משפט 3: משפט ההיררכיה במקום

תהיינה $f,g:\mathbb N\to\mathbb N$. נניח כי

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

אז $\mathrm{DSpace}(g)\subsetneq\mathrm{DSpace}(f)$.

מבנה ההוכחה. "$A$ מוכלת ממש ב-$B$" פירושו "$A\subseteq B$ וגם $B\not\subseteq A$". לכן צריך להוכיח שני דברים נפרדים:

• (א) $\mathrm{DSpace}(g)\subseteq\mathrm{DSpace}(f)$;
• (ב) $\mathrm{DSpace}(f)\not\subseteq\mathrm{DSpace}(g)$, כלומר קיימת שפה $A\in\mathrm{DSpace}(f)$ עם $A\notin\mathrm{DSpace}(g)$.

חלק (ב) הוא טענת קיום, ולכן נציג שפה קונקרטית — את $S_f$ — ונוכיח עליה שני דברים בלתי תלויים: שהיא ב-$\mathrm{DSpace}(f)$, ושהיא לא ב-$\mathrm{DSpace}(g)$.

חלק (א): ההכלה

$g=o(f)$ גורר $g=O(f)$ (אור קטן תמיד גורר אור גדול). לפי הטענה מהשיעור 2, $\mathrm{DSpace}(g)\subseteq\mathrm{DSpace}(f)$. $\square$

זהו — החלק הזה נגמר בשורה אחת, וכל שאר ההוכחה עוסקת בחלק (ב).

חלק (ב1): $S_f\in\mathrm{DSpace}(f)$

לפי ההגדרה, צריך להציג מכונה וקבוע, ולהראות שהמכונה מכריעה את $S_f$ ושהיא עושה זאת במקום שאינו עולה על הקבוע כפול $f$.

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

על קלט $\langle M\rangle$ שהוא קידוד של מכונה, $M_f$ פועלת כך:

1. אתחול מונה המקום. $M_f$ כותבת על סרט מונה המקום $\dfrac{f(|\langle M\rangle|)}{\lg|\Gamma_M|}$ אפסים. את המונה הזה חושבים כמספר באונרית.
2. אתחול מונה הזמן. $M_f$ כותבת על סרט מונה הזמן $3f(|\langle M\rangle|)$ אפסים, ומשמאלם $1$. את המונה הזה חושבים כמספר בבינארית — כלומר זהו הייצוג הבינארי של $2^{3f(|\langle M\rangle|)}$.
3. סימולציה. $M_f$ מסמלצת את ריצת $M_U$ על הקלט $\langle M,M\rangle$, כלומר מריצה את $M$ על הקידוד של עצמה, עם שתי תוספות:
   • בכל צעד ש-$M_U$ מסמלצת בריצה של $M$ על $\langle M\rangle$ — $M_f$ מורידה $1$ ממונה הזמן (בבינארית).
   • בכל פעם ש-$M$ כותבת בתא שעדיין לא כתבה בו — $M_f$ מוחקת אפס אחד ממונה המקום.
   • אם אחד המונים היה אמור לרדת מתחת לאפס — $M_f$ דוחה מיד ועוצרת את הסימולציה.
4. סיום. אם הסימולציה הסתיימה: אם $M$ דחתה את $\langle M\rangle$ אז $M_f$ מקבלת; אם $M$ קיבלה את $\langle M\rangle$ אז $M_f$ דוחה.

הערות טכניות על הבנייה:

• מדוע מונה הזמן בבינארית ומונה המקום באונרית? אילו כתבנו את $2^{3f}$ באונרית היינו צריכים $2^{3f(n)}$ תאים — הרבה מעבר לתקציב. בבינארית זה $3f(n)+1$ תאים בלבד. במונה המקום המספר עצמו הוא כבר בסדר גודל $f$, ולכן אונרי או בינארי אינו קריטי שם, והאונרי נוח יותר לספירה.
• איך יודעים אם $M$ כתבה בתא חדש? מסמנים תאים שכבר נכתב בהם, על ידי שינוי קל של אלפבית הסרט — טכניקה שראינו בחישוביות. אם $M$ כותבת שוב בתא מסומן, לא מורידים מהמונה.

ניתוח סמנטי: $M_f$ מכריעה את $S_f$.

כיוון ראשון: אם $\langle M\rangle\in S_f$ אז $M_f$ מקבלת. מהשייכות נובעים שני דברים: $M$ דוחה את $\langle M\rangle$ (ובפרט עוצרת עליו), וגם $\mathrm{space}_M(\langle M\rangle)\le f(|\langle M\rangle|)/\lg|\Gamma_M|$.

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

לגבי מונה הזמן: מכיוון ש-$M$ עוצרת על $\langle M\rangle$, נשתמש בחסם ספירת הקונפיגורציות מהשיעור 1:

נחסום כל אחד משלושת המחוברים בנפרד:

• נסמן ב-$N$ את מספר האפשרויות שהקידוד מתאר. אז $\lg|Q_M|\le \lg N\le|\langle M\rangle|$ — מספר המצבים אינו עולה על $N$, ולוגריתם של מספר אינו עולה על אורך הקידוד שלו. ואז, מהסופר־לינאריות, $|\langle M\rangle|\le f(|\langle M\rangle|)$.
• $\lg|\Gamma_M|\cdot \mathrm{space}_M(\langle M\rangle)\ \le\ \lg|\Gamma_M|\cdot\dfrac{f(|\langle M\rangle|)}{\lg|\Gamma_M|}=f(|\langle M\rangle|)$. כאן מצטמצם ה-$\lg|\Gamma_M|$ — זו כל הסיבה שהוא הוכנס להגדרת השפה מלכתחילה.
• $\lg \mathrm{space}_M(\langle M\rangle)\le \mathrm{space}_M(\langle M\rangle)\le f(|\langle M\rangle|)$ — לוגריתם של מספר אינו עולה על המספר, והמקום כבר חסום ב-$f$ (שהרי $\lg|\Gamma_M|\ge1$).

בסך הכול

שזה בדיוק המספר שרשום במונה הזמן. לכן גם מונה הזמן לא ירד מתחת לאפס, הסימולציה מסתיימת, $M_f$ מגיעה לשלב 4, מגלה ש-$M$ דחתה את $\langle M\rangle$ — ומקבלת.

כיוון שני: אם $\langle M\rangle\notin S_f$ אז $M_f$ דוחה. שלילת השייכות אומרת: $M$ אינה דוחה את $\langle M\rangle$, או שהמקום שלה עולה על החסם. נפצל:

• מקרה 1: $\mathrm{space}_M(\langle M\rangle)>\dfrac{f(|\langle M\rangle|)}{\lg|\Gamma_M|}$. אז במהלך הסימולציה מונה המקום ירד מתחת לאפס, ולפי שלב 3 $M_f$ דוחה.
• מקרה 2: המקום כן חסום, ולכן בהכרח $M$ אינה דוחה את $\langle M\rangle$. שימו לב — "אינה דוחה" אינו אותו דבר כמו "מקבלת"; ייתכן גם שהיא לא עוצרת. לכן נפצל שוב:
  • מקרה 2.1: $M$ אינה עוצרת על $\langle M\rangle$. לפי החסם שלמעלה בקונטרפוזיטיב: אם המקום חסום ב-$f/\lg|\Gamma_M|$ ומספר הצעדים עולה על $2^{3f(|\langle M\rangle|)}$, אז חייבת לחזור קונפיגורציה, ולכן המכונה בלולאה אינסופית. במקרה שלנו המכונה אכן לא עוצרת, ולכן היא בהכרח תעבור את $2^{3f(|\langle M\rangle|)}$ צעדים, מונה הזמן ירד מתחת לאפס, ו-$M_f$ דוחה.
  • מקרה 2.2: $M$ עוצרת ואינה דוחה, כלומר מקבלת. אז המונים לא נגמרים (כמו בחשבון הכיוון הראשון), הסימולציה מסתיימת, $M_f$ מגיעה לשלב 4, מגלה ש-$M$ קיבלה — ודוחה.

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

בשני הכיוונים יחד: $M_f$ מכריעה את $S_f$.

חשבון המקום. עכשיו צריך לחסום את המקום ש-$M_f$ דורשת. יש שלושה מקורות: כתיבת מונה המקום, כתיבת מונה הזמן, והסימולציה. חשוב: לא מספיק לספור את המקום שהמונה תופס בסוף, אלא גם את המקום שנדרש כדי לחשב אותו.

• קיים $\alpha>0$ כך שלכל מכונה $M$ ניתן לחשב את $\dfrac{f(|\langle M\rangle|)}{\lg|\Gamma_M|}$ במקום שאינו עולה על $\alpha\cdot f(|\langle M\rangle|)$. זה נובע מכך ש-$f$ ישימה במקום (כאן, ורק כאן, נכנס התנאי השני של המשפט): את $\lg|\Gamma_M|$ אפשר לקרוא מיידית מהקידוד — זה פשוט אורך הקידוד של תו בודד — והחילוק הוא פונקציה אלמנטרית, ולכן זול.
• קיים $\beta>0$ כך שלכל $M$ ניתן לחשב את $3f(|\langle M\rangle|)$ במקום שאינו עולה על $3\beta\cdot f(|\langle M\rangle|)$. שוב מהישימות במקום.
• קיים $\gamma>0$ כך שלכל $M$, המקום שהסימולציה (המבוקרת!) של האוניברסלית דורשת מקיים

ה-$\min$ מופיע מפני שאנחנו קוטעים את האוניברסלית ברגע שמונה המקום נגמר — היא לעולם לא תעבור את הסף, גם אם $M$ עצמה הייתה זוללת יותר. מכאן, כשבוחרים את האיבר הנוח מתוך ה-$\min$:

כאשר במעבר האמצעי השתמשנו שוב בסופר־לינאריות ($|\langle M\rangle|\le f(|\langle M\rangle|)$).

בסך הכול, לכל מכונה $M$:

המרה למכונה סטנדרטית. דקות אחת אחרונה: $M_f$ רב־סרטית, וההגדרה של $\mathrm{DSpace}$ מדברת על מכונה סטנדרטית. לפי משפט השקילות בין המודלים קיימת מכונה חד־סרטית $\hat M_f$, שקולה סמנטית ל-$M_f$, וקיים $\hat c>0$ כך שלכל $M$:

נגדיר $c=\hat c\,(\alpha+3\beta+3\gamma)$. אז $\hat M_f$ מכריעה את $S_f$ (כי היא שקולה סמנטית ל-$M_f$), ולכל $M$:

לכן $S_f\in\mathrm{DSpace}(f)$. $\square$

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

חלק (ב2): $S_f\notin\mathrm{DSpace}(g)$

זו תוצאה שלילית, ולכן — הוכחה בשלילה. (המרצה הדגיש שהוא בדרך כלל לא אוהב הוכחות בשלילה, אבל כשרוצים להראות שמשהו לא קורה, ההוכחה בשלילה שם for a reason.)

נניח בשלילה ש-$S_f\in\mathrm{DSpace}(g)$. אז לפי ההגדרה קיימת מכונה $M_g$ וקיים קבוע $c>0$ כך ש:

• $M_g$ מכריעה את $S_f$;
• לכל מכונה $M$: $\mathrm{space}_{M_g}(\langle M\rangle)\le c\cdot g(|\langle M\rangle|)$.

שימו לב מה יש לנו עכשיו ביד: את $M_g$ ואת $c$. שניהם קבועים מבחינת ההוכחה מרגע זה ואילך. זו נקודה שתשמש אותנו מיד.

כאן — ורק כאן — נכנס $g=o(f)$. מהגדרת $o$ קטן,

מהגדרת הגבול, לכל $\varepsilon>0$ קיים $n_0$ כך שלכל $n\ge n_0$ מתקיים $g(n)/f(n)<\varepsilon$. נבחר

הבחירה חוקית מפני ש-$c$ ו-$M_g$ כבר ידועים לנו בנקודה הזו — הם קבועים, לא משתנים שתלויים ב-$n$. נקבל: קיים $n_0\in\mathbb N$ כך שלכל $n\ge n_0$,

הבעיה שנשארה, והטריק. אנחנו רוצים להפעיל את אי־השוויון הזה על המכונה שביד — אבל $M_g$ היא מכונה ספציפית, ואולי הקידוד שלה קצר מ-$n_0$. הגבול מבטיח משהו רק עבור קלטים ארוכים מספיק. הפתרון: לנפח את המכונה מבלי לשנות אותה.

נגדיר מכונה $\hat M_g$, זהה ל-$M_g$ לחלוטין, אלא שהוספנו לה $n_0$ מצבי סרק — מצבים שלעולם לא נגיע אליהם. אז:

• $\hat M_g$ פועלת בדיוק כמו $M_g$ על כל קלט (לא שינינו שום דבר במצבים הקיימים ולא בפונקציית המעברים המהותית), ובפרט היא מכריעה את $S_f$;
• $|\langle \hat M_g\rangle|\ge n_0$ — כי טבלת המעברים גדלה, והקידוד איתה;
• הכי חשוב: $\Gamma_{M_g}=\Gamma_{\hat M_g}$ — לא נגענו באלפבית. זו הסיבה שניפחנו דווקא במצבים ולא בתווים.

עכשיו נריץ את $\hat M_g$ על הקידוד של עצמה. שני מקרים.

מקרה 1: $\hat M_g$ מקבלת את $\langle\hat M_g\rangle$. מכיוון ש-$\hat M_g$ מכריעה את $S_f$, מהקבלה נובע $\langle\hat M_g\rangle\in S_f$. אבל ההגדרה של $S_f$ דורשת, בין השאר, שהמכונה תדחה את הקידוד של עצמה. סתירה.

מקרה 2: $\hat M_g$ דוחה את $\langle\hat M_g\rangle$. מהסמנטיקה, $\langle\hat M_g\rangle\notin S_f$. תנאי השייכות ל-$S_f$ הוא "וגם" של שני תנאים; אנחנו יודעים שהתנאי הראשון (דוחה את עצמה) כן מתקיים, ולכן בהכרח התנאי השני נכשל:

מצד שני נחשב את אותו גודל מלמעלה. ראשית, מכיוון ש-$\hat M_g$ פועלת בדיוק כמו $M_g$ (הקלט לא משתנה, רק המכונה שמריצה אותו):

שנית, מכיוון ש-$|\langle\hat M_g\rangle|\ge n_0$ — וזו בדיוק הסיבה שניפחנו — מותר להציב באי־שוויון הגבול:

כאשר המעבר האחרון הוא רק החלפת $\Gamma_{M_g}$ ב-$\Gamma_{\hat M_g}$ — מותרת כי הם אותו אלפבית בדיוק. נכפיל ב-$c$:

יחד עם $(*)$ קיבלנו

כלומר גודל גדול ממש מעצמו. סתירה.

בשני המקרים הגענו לסתירה, ולכן ההנחה בשלילה בטלה: $S_f\notin\mathrm{DSpace}(g)$. $\square$

יחד עם חלק (ב1), $S_f\in\mathrm{DSpace}(f)\setminus\mathrm{DSpace}(g)$, ועם חלק (א) — $\mathrm{DSpace}(g)\subsetneq\mathrm{DSpace}(f)$. $\blacksquare$

סיכום הרעיון בשורה אחת: כל מכונה שחסומה במקום $O(g)$ מקיימת אוטומטית (אחרי ניפוח) את תנאי המקום של $S_f$, ולכן נשארת לכודה בסתירת הלכסון הטהורה — היא לא יכולה לא לקבל ולא לדחות את הקידוד של עצמה. מכונות שמעל הסף בורחות, ולכן $S_f$ כן כריעה — רק לא בתקציב $g$.

משפט 4: משפט ההיררכיה בזמן

תהיינה $f,g:\mathbb N\to\mathbb N$. נניח כי

1. $g=o(f)$;
2. $f$ ישימה בזמן;
3. $f$ סופר־לינארית.

אז $\mathrm{DTime}(g)\subsetneq\mathrm{DTime}\!\left(f^{\,2}\right)$.

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

מאיפה צומח הריבוע?

מהמעבר מהמכונה הרב־סרטית למכונה הסטנדרטית. בהוכחה במקום, המכונה $M_f$ שבנינו הייתה רב־סרטית, וההמרה למכונה חד־סרטית עלתה לנו רק בקבוע כפלי במקום — ולכן נשארנו ב-$\mathrm{DSpace}(f)$. בזמן, ההמרה עולה ריבוע.

ולמה ההמרה עולה ריבוע? כי המכונה החד־סרטית צריכה לרוץ קדימה ואחורה על פני כל האזור שבו יושבים "הסרטים" הרב־סרטיים המדומים, ולכן כל צעד מדומה עולה כמו רוחב האזור, כלומר כמו המקום. וכיוון שאין לנו שום מידע על המקום, החסם הטוב ביותר שאפשר לתת למקום הוא הזמן עצמו — ומכפלת זמן במקום נותנת $O(t^2)$.

הפער השני: אי אפשר לנפח מצבים

בהוכחה במקום, השלב הקריטי היה ניפוח הקידוד בלי לשנות את האלפבית, כי המכנה בהגדרת השפה היה $\lg|\Gamma_M|$. בזמן, המדד של האוניברסלית הוא

כלומר על כל צעד מסומלץ משלמים לא $\lg|\Gamma_M|$ אלא את כל אורך הקידוד $|\langle M\rangle|$. לכן, כדי שהצמצום יעבוד, השפה המקבילה חייבת להיראות כך:

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

הפתרון (כפי שנאמר בהרצה כדי לתת כיוון לתרגיל הבית): מגדירים את השפה על קלטים מהצורה $\langle M\rangle\#^k$ — קידוד של מכונה עם ריפוד מלאכותי של סולמיות. עכשיו אפשר להאריך את הקלט כרצוננו, ובכך להגדיל את $n$ ולהיכנס לתחום שבו הגבול תופס, בלי להגדיל את $|\langle M\rangle|$ שיושב במכנה. ההגדרה המדויקת של השפה המרופדת תינתן בתרגיל.

משפט 5 (מסקנה): $\mathrm P\subsetneq\mathrm{EXP}$

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

הכלה נשמרת תחת איחוד. הכלה ממש — לא.

נגד־דוגמה: $A_1=\{1\}$, $A_2=\{2\}$, $C=\{1,2\}$. אז $A_1\subsetneq C$ וגם $A_2\subsetneq C$, אבל $A_1\cup A_2=C$ ואינו מוכל ממש ב-$C$.

בשפה של המשפטים: מהמשפט קל לקבל "לכל $c$ קיימת שפה $A\in\mathrm{EXP}$ שאינה ב-$\mathrm{DTime}(n^c)$", אבל מה שצריך זה "קיימת שפה $A\in\mathrm{EXP}$ שלכל $c$ אינה ב-$\mathrm{DTime}(n^c)$". שני המשפטים אינם שקולים — השני גורר את הראשון, לא להפך.

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

הוכחה.

שלב 1 — ההכלה $\mathrm P\subseteq\mathrm{EXP}$. כבר יש: הראינו $\mathrm P\subseteq\mathrm{PSPACE}$ (שיעור 2) ו-$\mathrm{PSPACE}\subseteq\mathrm{EXP}$ (משפט 1 לעיל).

שלב 2 — מעבר למחלקה עדינה מלמטה. יהי $c\ge 1$. אז $n^c=O(2^n)$ (למעשה אפילו $o(2^n)$, אבל $O$ מספיק כאן), ולכן $\mathrm{DTime}(n^c)\subseteq\mathrm{DTime}(2^n)$. זה נכון לכל $c$, והכלה רגילה כן נשמרת תחת איחוד, ולכן

שלב 3 — הפעלת משפט ההיררכיה בזמן. נסמן

נבדוק את שלושת התנאים:

1. $g=o(f)$: אכן, $\dfrac{2^n}{2^{2n}}=2^{-n}\xrightarrow[n\to\infty]{}0$.
2. $f$ אלמנטרית ולכן ישימה בזמן.
3. $f$ סופר־לינארית: $2^{2n}\ge n$ לכל $n$.

לכן ממשפט ההיררכיה בזמן,

שלב 4 — מעבר למחלקה גסה מלמעלה. $2^{4n}=O\!\left(2^{n^2}\right)$ (כי $4n\le n^2$ לכל $n\ge4$), ולכן

הצעד האחרון הוא פשוט "לקלף את האיחוד" בכיוון ההפוך: $2^{n^2}$ הוא מהצורה $2^{n^c}$ עם $c=2$.

שלב 5 — הרכבה.

בשרשרת הכלות שבה לפחות חוליה אחת היא הכלה ממש, ההרכבה כולה היא הכלה ממש. לכן $\mathrm P\subsetneq\mathrm{EXP}$. $\blacksquare$

משפט 6 (מסקנה מהמסקנה): אחת משתי ההכלות היא ממש — ולא יודעים איזו

אנחנו יודעים:

אילו שתי ההכלות היו שוויונות, היה נובע $\mathrm P=\mathrm{EXP}$ — בסתירה למשפט 5. לכן לפחות אחת מבין $\mathrm P\subseteq\mathrm{PSPACE}$ ו-$\mathrm{PSPACE}\subseteq\mathrm{EXP}$ היא הכלה ממש.

אבל אף אחד לא יודע איזו. שתי השאלות — האם $\mathrm P=\mathrm{PSPACE}$ והאם $\mathrm{PSPACE}=\mathrm{EXP}$ — הן בעיות פתוחות. המשפטים האלה ידועים כבר עשרות שנים ולא הצליחו להתקדם. זו טעימה ראשונה מהאופי של התחום: יודעים משהו חלקי, ולא יודעים לחדד אותו.

הערה מהשיעור [02:16:59]: לשאלת סטודנט — לא, מחשבי־על ולא מחשבים קוונטיים לא "יפתרו" את זה. זו שאלה מתמטית על גבולות של מודל חישוב, לא שאלה של כוח חישוב.

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

דוגמה 1: מעקב מספרי אחר המונים של $M_f$

ניקח $f(n)=n^2$ (סופר־לינארית וישימה במקום — פולינום). תהי $M$ מכונה שהקידוד שלה באורך $|\langle M\rangle|=100$ ואלפבית הסרט שלה בגודל $|\Gamma_M|=4$, כלומר $\lg|\Gamma_M|=2$.

• מונה המקום מאותחל ל-$\dfrac{f(100)}{2}=\dfrac{10{,}000}{2}=5{,}000$ אפסים.
• מונה הזמן מאותחל ל-$3f(100)=30{,}000$ אפסים ומשמאלם $1$ — כלומר הייצוג הבינארי של $2^{30{,}000}$, ב-$30{,}001$ תאים בלבד. (באונרית זה היה דורש $2^{30{,}000}$ תאים — בלתי אפשרי.)
• אם $M$ על $\langle M\rangle$ כותבת ב-$4{,}000$ תאים שונים ועוצרת אחרי $10^9$ צעדים: שני המונים שורדים ($4{,}000\le 5{,}000$ ו-$10^9\ll 2^{30{,}000}$), ולכן $M_f$ תסמלץ עד הסוף ותהפוך את התשובה.
• אם $M$ כותבת ב-$6{,}000$ תאים: מונה המקום נגמר, $M_f$ דוחה — וזה נכון, כי $6{,}000>5{,}000$ ולכן $\langle M\rangle\notin S_f$.
• אם $M$ נכנסת ללולאה אינסופית תוך שימוש ב-$3{,}000$ תאים בלבד: מספר הקונפיגורציות שלה חסום ב-$2^{3f(100)}$, ולכן היא חייבת לחזור על קונפיגורציה. מונה הזמן יגיע ל-$0$ ו-$M_f$ תדחה. אכן $\langle M\rangle\notin S_f$, כי מכונה שאינה עוצרת אינה "דוחה".

דוגמה 2: התרגיל שהמרצה נתן לכיתה — לבחור $f$ ו-$g$ נכונות

המרצה ביקש מהכיתה למצוא $f,g$ שיוכיחו $\mathrm P\subsetneq\mathrm{EXP}$. הכיתה הציעה שלושה ניסיונות, ושניים מהם נכשלו — ההסבר לכישלון חשוב יותר מהתשובה.

• ניסיון א׳: $f(n)=n^2$, $g(n)=n$. תקין מתמטית: $g=o(f)$, $f$ ישימה בזמן וסופר־לינארית, ולכן $\mathrm{DTime}(n)\subsetneq\mathrm{DTime}(n^4)$. אבל חסר תועלת — שתי המחלקות יושבות עמוק בתוך $\mathrm P$ ואינן אומרות דבר על $\mathrm{EXP}$.
• ניסיון ב׳: $f(n)=2^n$, $g(n)=n$. מקבלים $\mathrm{DTime}(n)\subsetneq\mathrm{DTime}(2^{2n})$. שוב תקין ושוב חסר תועלת: $\mathrm{DTime}(n)$ אינו מכיל את כל $\mathrm P$, ולכן לא הוכחנו כלום על $\mathrm P$.
• ניסיון ג׳ (הכיוון הנכון): $g(n)=2^n$. קודם מראים ש-$\mathrm P\subseteq\mathrm{DTime}(2^n)$ — כי לכל $c$, $n^c=O(2^n)$, והכלה נשמרת תחת איחוד. עכשיו $\mathrm{DTime}(2^n)$ היא מחלקה עדינה שמכילה את כל $\mathrm P$, ואפשר להפעיל עליה את המשפט.

תרגיל־בזק שנשאל בכיתה: האם מותר לקחת $f(n)=2^{n+1}$? לא. $\dfrac{g(n)}{f(n)}=\dfrac{2^n}{2^{n+1}}=\dfrac12$, שאינו שואף ל-$0$. לכן $g\ne o(f)$ והמשפט אינו חל. צריך פער בסדר גודל, לא פער בקבוע — וזו בדיוק הנקודה שקבוע כפלי בחזקה כן משנה סדר גודל, אבל קבוע כפלי מחוץ לחזקה לא.

דוגמה 3: היכן הטיעון "איבר־איבר" נשבר

ההוכחה השגויה: "לכל $c\ge 1$ מתקיים $n^c=o(2^{n^c})$, ולכן $\mathrm{DTime}(n^c)\subsetneq\mathrm{DTime}(2^{n^c})$; מכיוון שזה נכון לכל $c$, גם האיחודים מקיימים $\mathrm P\subsetneq\mathrm{EXP}$."

מה בדיוק שגוי: מה שהוכחנו הוא "לכל $c$ קיימת $A_c\in\mathrm{EXP}$ שאינה ב-$\mathrm{DTime}(n^c)$". ה-$A_c$ הזו תלויה ב-$c$. ייתכן ש-$A_1\in\mathrm{DTime}(n^2)$, ש-$A_2\in\mathrm{DTime}(n^3)$, וכן הלאה — ואז כל אחת מהן בכל זאת נמצאת ב-$\mathrm P$, ולא הוכחנו כלום. מה שצריך הוא שפה אחת שבורחת מכל המחלקות בבת אחת, וזה בדיוק מה שהמעבר דרך $\mathrm{DTime}(2^n)$ נותן: שפה אחת שאינה ב-$\mathrm{DTime}(2^n)\supseteq\mathrm P$.

זו הנקודה שהודגמה בכיתה עם $\{1\}\subsetneq\{1,2\}$ ו-$\{2\}\subsetneq\{1,2\}$ אבל $\{1\}\cup\{2\}=\{1,2\}$.

דוגמה 4: יישום ישיר של משפט ההיררכיה במקום

בדיקת התנאים: $g(n)=n$, $f(n)=n^2$; $\dfrac{n}{n^2}=\dfrac1n\to0$ ולכן $g=o(f)$; $f$ פולינום ולכן ישימה במקום; $f(n)=n^2\ge n$ ולכן סופר־לינארית. שלושת התנאים מתקיימים, המשפט חל. שימו לב שבמקום אין ריבוע — התוצאה היא $\mathrm{DSpace}(f)$ ולא $\mathrm{DSpace}(f^2)$. אילו הייתה זו שאלת זמן, היינו מקבלים רק $\mathrm{DTime}(n)\subsetneq\mathrm{DTime}(n^4)$.