סיבוכיות מקום

חישוב חסום־מקום, נגישות בגרף קונפיגורציות ומשפט סביץ'.

מטרות

• להגדיר מקום דטרמיניסטי ואי־דטרמיניסטי עם קלט לקריאה בלבד.
• להשתמש בגרפי קונפיגורציות להוכחות שייכות ושלמות.
• להרכיב רדוקציות מקום לוגריתמי בלי לשמור את פלט הביניים.
• לגזור במלואה את רקורסיית סביץ' ואת חסם המקום.
• להסביר את $\mathrm{NL}=\mathrm{coNL}$ ואת $\mathrm{NPSPACE}=\mathrm{PSPACE}$ בזהירות.

1. המודל ומה סופרים

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

מכריע אי־דטרמיניסטי חייב לעצור בכל ענף ולעמוד בחסם בכל ענף. מקום ניתן לשימוש חוזר, ולכן חישוב במקום פולינומי עשוי לרוץ זמן מעריכי. כאשר $s(n)\ge\log n$, אפשר למחוק לולאות ממסלול קבלה קצר ביותר, ולכן אורכו אינו עולה על מספר הקונפיגורציות.

2. גרף קונפיגורציות

קונפיגורציה שומרת מצב בקרה, מיקום ראש הקלט, תוכן אזור העבודה ומיקומי ראשי העבודה. עבור אלפבית וקבוצת מצבים קבועים, למכונת מקום $s(n)$ יש

קונפיגורציות, בהנחה $s(n)\ge\log n$. בגרף הקונפיגורציות יש קודקוד לכל קונפיגורציה חוקית וקשת לכל מעבר חוקי יחיד. המכונה מקבלת אם ורק אם יש מסלול מקונפיגורציית ההתחלה לקונפיגורציית קבלה.

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

3. STCON היא הבעיה הקנונית של NL

STCON שואלת אם בגרף מכוון יש מסלול מקודקוד מסומן $s$ לקודקוד $t$.

שייכות ל-NL. שומרים קודקוד נוכחי ומונה עד $|V|$, מנחשים שכן, מאמתים את הקשת ומקבלים בהגעה ל-$t$. אם יש מסלול, יש מסלול פשוט באורך לכל היותר $|V|-1$; המונה מונע ענפים אינסופיים. שם קודקוד ומונה דורשים $O(\log|V|)$ ביטים.

NL-קושי. תהי $A\in\mathrm{NL}$ ומכונה $M$ המכריעה אותה. ממפים $x$ לגרף הקונפיגורציות $G_{M,x}$ עם קודקודי התחלה וקבלה. הקבלה היא נגישות. הרדוקציה אינה שומרת את הגרף: טרנסדיוסר לוגריתמי מונה שמות קונפיגורציות וזוגות קשתות בעזרת מונים, ומחשב מחדש כל מעבר מקומי. קונפיגורציה של מכונת log-space מכילה $O(\log n)$ ביטים. לכן זו רדוקציית many-one במקום לוגריתמי, ו-STCON היא NL-שלמה.

4. רדוקציות לוגריתמיות והרכבה

$A\le_m^{\mathrm L}B$ אם טרנסדיוסר דטרמיניסטי במקום לוגריתמי מחשב $f$ כך ש-

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

בהרכבת $f$ ו-$g$, המחרוזת $f(x)$ עלולה להיות ארוכה מכדי לשמור. מסמלצים את $g$; בכל פעם שהוא מבקש את התו ה-$i$ בקלט, מריצים מחדש את $f$ עם מונה עד הפקת התו ה-$i$. שומרים רק את קונפיגורציית $g$, האינדקס וקונפיגורציית $f$. מאורך פלט פולינומי נובע $\log|f(x)|=O(\log n)$. לכן רדוקציות לוגריתמיות סגורות להרכבה באמצעות חישוב מחדש.

כדי להוכיח ש-$B$ היא NL-שלמה, מראים $B\in\mathrm{NL}$ ומרדדים אליה בעיה NL-שלמה, לרוב STCON. רדוקציה פולינומית בלבד אינה מספיקה.

5. משפט סביץ': הרקורסיה המלאה

משפט סביץ'. לפונקציית מקום ניתנת לבנייה $s(n)\ge\log n$, $\mathrm{NSPACE}(s(n))\subseteq\mathrm{DSPACE}(s(n)^2).$

תהי $M$ מכונה המשתמשת ב-$O(s)$ מקום אי־דטרמיניסטי, עם לכל היותר $N=2^{cs}$ קונפיגורציות. נגדיר

בבסיס $\ell=0$: מקבלים אם $u=v$ או אם $(u,v)$ הוא מעבר יחיד. עבור $\ell>0$ מונים כל קונפיגורציית אמצע $m$ ומקבלים אם שתי הקריאות

מקבלות. מסלול באורך $2^\ell$ ניתן לחצייה באמצע; ובכיוון השני שרשור שני המסלולים נותן מסלול באורך המותר.

קוראים עם $\ell=\lceil\log N\rceil=O(s)$. בכל רמה שומרים $u,v,m$, את $\ell$ ומונה: יחד $O(s)$ ביטים. שתי הקריאות מתבצעות זו אחר זו, והמקום משמש מחדש בין מועמדי אמצע. לכן

הזמן עצום, בערך $N^{O(\log N)}=2^{O(s^2)}$, אך המשפט עוסק במקום. הכפלה במספר הענפים מנתחת זמן, לא מקום.

עבור $s(n)=n^k$ מתקבל $\mathrm{NPSPACE}\subseteq\mathrm{PSPACE}$. הכיוון ההפוך מיידי כי דטרמיניזם הוא מקרה פרטי של אי־דטרמיניזם. לכן

לעומת זאת, עבור מקום לוגריתמי סביץ' נותן רק $\mathrm{NL}\subseteq\mathrm{SPACE}(\log^2n)$; הוא אינו מוכיח $\mathrm L=\mathrm{NL}$.

6. משפט המשלים

משפט אימרמן–סלפשצ'ני. $\mathrm{NL}=\mathrm{coNL}$; בכלליות, $\mathrm{NSPACE}(s(n))$ סגורה למשלים כאשר $s(n)\ge\log n$.

המשפט עצמו הוא חומר מרכזי; הוכחת הספירה האינדוקטיבית המלאה ארוכה יותר מהוכחת סביץ'. הרעיון הוא לאמת אי־נגישות בלי לרשום את כל הקודקודים שהושגו. נסמן ב-$R_i$ את הקודקודים הנגישים מ-$s$ בתוך $i$ צעדים. מאמתים אי־דטרמיניסטית את המספר המדויק $|R_i|$ מתוך $|R_{i-1}|$ באמצעות מעבר על כל הקודקודים ועדי נגישות באורך $i-1$. לאחר שהספירה המדויקת מאומתת, בודקים ש-$t$ אינו ביניהם. המונים ושם קודקוד דורשים מקום לוגריתמי.

הנקודה המפתיעה היא שאי־דטרמיניזם מאמת עובדה שלילית הנראית אוניברסלית דרך ספירה מדויקת. ״ננחש שאין מסלול״ אינו עד.

דוגמה פתורה

בגרף עם הקשתות $1\to2$, $2\to3$, $1\to4$, מכונת STCON יכולה לנחש $1,2,3$ כדי לקבל את $(1,3)$. היא שומרת רק קודקוד נוכחי ומונה, לא את המסלול. ברקורסיית סביץ' עם חסם אורך ארבע אפשר לנסות $m=2$, ולהוכיח רקורסיבית $1\leadsto2$ ו-$2\leadsto3$ באורך לכל היותר שניים. ניסיונות אמצע שנכשלו נמחקים לפני הבא.

בהרכבת רדוקציות, אם $f(x)$ מפיקה מטריצת שכנויות ו-$g$ קוראת את תאיה בסדר שרירותי, לא שומרים את המטריצה. כל בקשה לתא $i$ מריצה שוב את $f$ עד התו ה-$i$. הזמן גדל, המקום נשאר לוגריתמי.

טעויות נפוצות

• לחייב את סרט הקלט כמקום עבודה או להשתמש בפלט כזיכרון.
• להשמיט מונה צעדים מאלגוריתם STCON ולהשאיר ענפים שאינם עוצרים.
• לבנות בפועל את גרף הקונפיגורציות.
• להשתמש ברדוקציה פולינומית כשנדרשת שלמות תחת log-space.
• לשמור את $f(x)$ תוך טענה שסגרנו הרכבה לוגריתמית.
• להכפיל את ענפי סביץ' בתוך חסם המקום.
• לטעון שסביץ' מוכיח $\mathrm L=\mathrm{NL}$.
• לחשוב ש-$\mathrm{NL}=\mathrm{coNL}$ נובע פשוט מהחלפת מצבי קבלה ודחייה.

המחשות

מציגים זה לצד זה גרף קונפיגורציות מרומז ועץ רקורסיית סביץ', כאשר רק מסלול רקורסיבי פעיל אחד נמצא בזיכרון. בלוח נוסף $g$ מבקשת תו $i$, ו-$f$ ״משוחזרת״ עד הפקתו.

תרגילים

תרגיל 1 — מסלול קבלה קצר

הוכיחו שמסלול קבלה פשוט במכונת מקום $s(n)$ מכיל פחות מ-$N$ קונפיגורציות, כאשר $N$ הוא מספר הקונפיגורציות.

תרגיל 2 — מה שומרת מכונת NL ל-STCON

תארו את מצב העבודה של מכונת NL סטנדרטית ל-STCON וחסמו את המקום ב-$O(\log|V|)$.

תרגיל 3 — הרכבת רדוקציות לוגריתמיות

מדוע בהרכבה $\log|f(x)|=O(\log|x|)$ חיוני? מה משחזרים במקום לשמור?

תרגיל 4 — סביץ' ל-$O(s^2)$

פתרו את הרקורסיה $S(\ell)=S(\ell-1)+O(s)$ בעומק $\ell=O(s)$, והסיקו את חסם המקום של סביץ'.

תרגיל 5 — $\mathrm{NPSPACE}=\mathrm{PSPACE}$ ו-NL=coNL

הסיקו $\mathrm{NPSPACE}=\mathrm{PSPACE}$ מסביץ'. האם $\mathrm{NL}=\mathrm{coNL}$ גורר $\mathrm L=\mathrm{NL}$?

סיכום

מקום מובן דרך נגישות מרומזת. STCON לוכדת את NL; סביץ' מריבע מקום; NPSPACE=PSPACE; Immerman–Szelepcsényi נותן NL=coNL.

תרגול מודרך

משימה 1 — מספר קונפיגורציות ב-log-space

הוכיחו שלמכונת $O(\log n)$ מקום יש מספר פולינומי של קונפיגורציות.

משימה 2 — complete מול hard

הבחינו בין NL-hard ל-NL-complete. מתי רדוקציה ל-STCON מוכיחה שלמות?

משימה 3 — מתווה Immerman–Szelepcsényi

סכמו ברמת רעיון מדוע אי־נגישות ב-STCON ב-NL (בלי הוכחה מלאה).

נתיב מקורות וסמכות

• ראיות סטודנטיאליות/קורס: סיכומי שיעור/סיכום ממוזג.pdf, עמ׳ 101–130 ועמ׳ 142 (L/NL, נגישות, רדוקציות, סביץ' ומשלים). זהו סיכום סטודנטיאלי המשמש להתאמת קורס, לא סמכות למשפטים.
• סמכות ספרי לימוד: Sipser, מהדורה 3, פרק 8: §8.1 עמ׳ 333–336, §§8.4–8.5 עמ׳ 348–354, §8.6 עמ׳ 354–356; Arora–Barak, טיוטה, פרק 4, §§4.1–4.4, עמ׳ ספר 75–87; Papadimitriou, פרק 7, בפרט §7.3 עמ׳ 146–154, ופרק 16 §16.1 עמ׳ 395–399.
• מצב עריכתי: שוויוני המחלקות ורקורסיית סביץ' נבדקו מול סעיפים אלה. הוכחת NL=coNL מסומנת במפורש כמתווה. נבדק; ביטחון גבוה.