משפט אימרמן

משפט אימרמן (Immerman–Szelepcsényi) הוא תוצאה בתורת הסיבוכיות (ענף במדעי המחשב) המראה כי מחלקות סיבוכיות מקום אי דטרמיניסטיות סגורות לפעולת המשלים (בעוד אותה שאלה עבור סיבוכיות זמן עודנה פתוחה וככל הנראה התשובה לה שלילית). המשפט הוכח בשנת 1987 באופן בלתי תלוי בידי ניל אימרמן ו-Róbert Szelepcsényi, אשר זכו ב-1995 בפרס גדל על תוצאה זו.

באופן פורמלי, תוצאת המשפט היא כי לכל פונקציה $s(n)\geq \log(n)$ מתקיים $\ {\mbox{NSPACE}}\left(s(n)\right)={\mbox{co-NSPACE}}\left(s(n)\right)$ .

מבוא

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

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

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

ניתן לקחת כדוגמה לכך את האלגוריתם האי דטרמיניסטי הבודק האם מספר הוא פריק. אלגוריתם אי דטרמיניסטי לבעיה זו פועל כך על קלט $\ n$ ; הוא בוחר מספר $\ 2\leq a<n$ באופן אי דטרמיניסטי (דהיינו כל חישוב מתאפיין ב- $\ a$ אחר השייך לתחום) ובודק האם $\ a$ מחלק את $\ n$ פשוט על ידי חלוקה. אם $\ a$ חילק את $\ n$ , האלגוריתם עונה "כן", ואחרת הוא עונה "לא". אם $\ n$ פריק הרי שקיים $\ 2\leq a<n$ שמחלק אותו ולכן קיים חישוב שבו האלגוריתם האי דטרמיניסטי יגיד "כן", ואילו אם $\ n$ אינו פריק לא קיים $\ a$ שכזה ולכן לכל חישוב האלגוריתם יגיד "לא", כנדרש.

נביט על האלגוריתם ה"הפוך" לבעיה זו: האלגוריתם מבצע בדיקה זהה - בוחר $\ a$ ובודק האם $\ n$ מתחלק בו, ועונה "לא" אם כך הדבר ואחרת עונה "כן". אלא שאלגוריתם זה בבירור אינו אלגוריתם עבור בעיית הראשוניות^[1]; אמנם, אם $\ n$ ראשוני אז לכל $\ a$ שיבחר האלגוריתם יענה "כן", אך אם $\ n$ אינו ראשוני עדיין ייתכן שיהיו חישובים שבהם האלגוריתם עונה "כן", אם בחר $\ a$ שאינו מחלק את $\ n$ . למשל, אם נבחר $\ n=4$ שאינו ראשוני, והאלגוריתם בחר $\ a=3$ הוא יענה "כן", אף שהיה עליו לענות "לא".

מכיוון שבהינתן אלגוריתם אי דטרמיניסטי ניתן להמיר אותו תמיד באלגוריתם דטרמיניסטי ולהפך, מובטח כי לכל בעיה הניתנת לפתרון, ואפילו יהא זה פתרון אי דטרמיניסטי, ניתן לפתור גם את הבעיה ההפוכה באופן אי דטרמיניסטי. עם זאת, באופן כללי המרת אלגוריתם אי דטרמיניסטי בדטרמיניסטי מגדילה את כמות משאבי החישוב הנדרשים לפתרון הבעיה. מכאן עולה השאלה האם בהינתן בעיה שקיים לה פתרון אי דטרמיניסטי המשתמש בכמות מסוימת של משאבים קיים פתרון אי דטרמיניסטי לבעיה המשלימה שצורך את אותה כמות משאבים (או לפחות את אותו סדר גודל של כמות משאבים). כאשר שאלה זו מנוסחת עבור המשאב של זמן חישוב יעיל (פולינומי), מתקבלת למעשה השאלה האם המחלקה NP שווה למחלקה co-NP, שהיא שאלה פתוחה חשובה במדעי המחשב. משפט אימרמן עונה על השאלה עבור משאב הזיכרון - הוא מראה כי לכל פונקציה $\ s(n)$ "סבירה"^[2], אם בעיה ניתנת לפתרון אי דטרמיניסטי בסיבוכיות זיכרון של $\ O(s(n))$ אז גם הבעיה המשלימה ניתנת לפתרון אי דטרמיניסטי בסיבוכיות זיכרון זו. בניסוח פורמלי,

$\ {\mbox{NSPACE}}\left(s(n)\right)={\mbox{co-NSPACE}}\left(s(n)\right)$ .

תוצאת המשפט (והוכחתו) מזכירים את משפט סביץ' הפשוט יותר, המראה שכל בעיה הניתנת לפתרון באופן אי דטרמיניסטי בסיבוכיות זיכרון המיוצגת על ידי פונקציה "סבירה" $\ s(n)$ , ניתן לפתור את הבעיה באופן דטרמיניסטי תוך שימוש בכמות זיכרון של לכל היותר $\ s^{2}(n)$ , ובפרט שאם בעיה ניתנת לפתרון אי דטרמיניסטי תוך שימוש בכמות "יעילה" של זיכרון, היא ניתנת גם לפתרון דטרמיניסטי תוך שימוש בכמות יעילה שכזו של זיכרון. עם זאת, משפט אימרמן אינו תוצאה מיידית של משפט סביץ' שכן הוא "בזבזני" פחות - הוא אינו דורש הגדלה אסימפטוטית כלל של סיבוכיות הזיכרון על מנת לפתור את הבעיה המשלימה.

הוכחה

בדומה למשפט סביץ', הוכחת המשפט הכללי מסתמכת על פתרון בעיה ספציפית - בעיית הישִיגוּת בגרפים. בהינתן גרף מכוון $\ G$ בעל $\ n$ צמתים ושני צמתים $\ s,t$ , בעיית הישיגות היא השאלה האם קיים מסלול מ- $\ s$ אל $\ t$ בגרף. מכיוון שניתן לייצג חישוב כלשהו של אלגוריתם אי דטרמיניסטי בתור מסלול בגרף אשר מייצג את הקונפיגורציות האפשריות השונות בחישוב, ניתן לצמצם את השאלה האם האלגוריתם עונה "כן" על קלט מסוים לשאלה אם קיים בגרף הקונפיגורציות שמתאר את ריצתו על קלט זה מסלול מהקונפיגורציה ההתחלתית לקונפיגורציה שבה האלגוריתם עונה "כן" (ניתן להניח ללא הגבלת הכלליות כי קיימת רק אחת כזו).

בעיית הישיגות בגרף ניתנות לפתרון אי דטרמיניסטי בזיכרון $\ O(\log(n))$ ^[3]:

האלגוריתם מתחיל בצומת

\ s

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

\ t

הוא עוצר ועונה "כן"; אחרת, אם הוא ביצע למעלה מ-

\ n

צעדים, הוא עוצר ועונה "לא". צריכת הזיכרון של האלגוריתם נמוכה; על מנת לזכור את הצומת הנוכחי נדרש זיכרון של

\ O(\log(n))

, וגם כדי לספור את הצעדים נדרש זיכרון של

\ O(\log(n))

.

ההוכחה למשפט אימרמן מבוססת על כך שגם הבעיה המשלימה - הבדיקה האם בגרף לא קיים מסלול מ- $\ s$ אל $\ t$ - ניתנת לביצוע באופן אי דטרמיניסטי בזיכרון $\ O(\log(n))$ . כלומר, קיימת מכונת טיורינג לא-דטרמיניסטית שמקבלת כקלט את צומת המקור $\ s$ וצומת היעד $\ t$ ועונה "כן" אם $\ t$ אינו יָשִׁיג מ- $\ s$ (לפחות עבור בחירה אי-דטרמיניסטית יחידה שמבצע האלגוריתם). לעומת זאת אם קיים מסלול $\ s$ אל $\ t$ , האלגוריתם יענה "לא" בכל אחד מהחישובים שהוא מבצע בהתאם לבחירות האי-דטרמיניסטיות.

אימרמן הראה כי אם האלגוריתם יודע מראש מהו מספר הצמתים הישיגים מ- $\ s$ לכל היותר ב- $\ i$ צעדים (נסמן מספר זה ב $\ N_{i}$ ), אז האלגוריתם יכול פשוט "לנחש" את אותם צמתים ישיגים (ניחוש של $\ N_{i}$ צמתים שונים, למשל על ידי מעבר סדרתי על כל הצמתים ובחירה אי דטרמיניסטית אם רוצים לבחור אותו או לא), ופשוט לבדוק האם הם ישיגים מ $\ s$ (באופן אי-דטרמיניסטי, בזיכרון $\ O(\log(n))$ , כפי שתואר מעלה). במידה שאכן האלגוריתם בחר את $\ N_{i}$ הצמתים ה"נכונים" (אלו שבאמת ישיגים מ- $\ s$ ), הוא בודק האם הצומת $\ t$ הוא אחד מהם. אם $\ t$ אחד מהצמתים הישיגים, האלגוריתם עונה "לא", ואחרת עונה "כן". אם אחת הבדיקות במהלך הדרך נכשלה האלגוריתם מחזיר תשובה "לא" כברירת מחדל (למשל, במידה והוגרל צומת "לא נכון" עבור הקבוצה של $\ N_{i}$ הצמתים הישיגים).

לפי תיאור האלגוריתם, קל לראות שאם המספר $\ N_{i}$ ידוע לאלגוריתם, ו- $\ t$ אינו יָשיג מ- $\ s$ , אז קיימת בחירה שבה האלגוריתם יבחר בדיוק את $\ N_{i}$ הצמתים הישיגים מ- $\ s$ , יבדוק שכל אחד מהם אכן ישיג, יזהה ש- $\ t$ אינו אחד מהם, ויחזיר תשובה "כן" ואילו כאשר $\ t$ ישיג מ- $\ s$ (ב-i צעדים), אזי האלגוריתם יחזיר תשובה "לא" עבור כל אחת מהבחירות שהוא יכול לבצע: או שאלגוריתם יכשל באחת מבדיקות הביניים (ואז יחזיר "לא"), או שיצליח בכל הבחירות, יזהה את קבוצת $\ N_{i}$ הצמתים הישיגים מ- $\ s$ (ב-i צעדים), יבדוק שכל אחד מהם אכן יָשיג, ואז יזהה ש- $\ t$ ישיג מ- $\ s$ , ויחזיר תשובה "לא". הבדיקה המתוארת לעיל היא חסכונית מבחינת צריכת הזיכרון שלה - מעבר סדרתי על כל צומתי הגרף דורש רק $\ O(\log(n))$ זיכרון, וכך גם הבדיקות הנוספות שתיארנו.

מכאן עולה כי אם נתון המספר $\ N_{n}$ (הצמתים הישיגים ב- $n$ צעדים, כאשר $n$ הוא גודל הגרף), אז ניתן לפתור את הבעיה בזיכרון $\ O(\log(n))$ - פשוט מוודאים ש- $\ t$ אינו ישיג מ- $\ s$ ב- $\ n$ צעדים (ולכן אינו ישיג כלל). מכיוון שהסתמכנו על ידיעה מראש של $\ N_{n}$ , על מנת להשלים את האלגורים נותר להסביר כיצד ניתן לחשב את $\ N_{n}$ . החישוב מתבצע בצורה אינדוקטיבית, כלומר האלגוריתם מצליח לחשב את $\ N_{i+1}$ כאשר נתון לו המספר $\ N_{i}$ . מכיוון שהאלגוריתם אינו דטרמיניסטי, קיימת עבורו האפשרות לענות "לא" אם החישוב לא הצליח, עקב ניחוש שגוי (כל עוד קיים לפחות ניחוש אחד שיהיה תקין ויוביל לתשובה "כן")

ראשית, ברור כי $\ N_{0}=1$ - על ידי מסלול מאורך 0 אפשר להגיע מ- $\ s$ רק אל $\ s$ עצמו. החישוב האינדוקטיבי (מ- $\ N_{i}$ ל- $\ N_{i+1}$ ) מתנהל באופן הבא: האלגוריתם עובר סדרתית על כל צומתי הגרף. לכל צומת $\ v$ הוא מחפש צומת $\ u$ כך שיש קשת מ- $\ u$ אל $\ v$ ובנוסף לכך קיים מסלול באורך $\ i$ לכל היותר מ- $\ s$ אל $\ u$ . חיפוש שכזה מתבצע באופן דומה למתואר לעיל - האלגוריתם בוחר באופן אי דטרמיניסטי את כל הצמתים שמרחקם מ- $\ s$ הוא לכל היותר $\ i$ , בודק שאכן נבחרו הצמתים הנכונים, ואז בודק אם ניתן להגיע מהם אל $\ v$ . כמקודם, דרישות הסיבוכיות של שלב זה הן $\ O(\log(n))$ . לבסוף, האלגוריתם מחזיק מונה הסופר את מספרם של הצמתים $\ v$ שקיימו את התנאי; לאחר שהאלגוריתם מסיים לעבור על כל צומתי הגרף, מספר זה הוא בדיוק $\ N_{i+1}$ . מכאן שניתן לחשב את $\ N_{n}$ באופן אינדוקטיבי.

לקריאה נוספת

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
N. Immerman, "Nondeterministic space is closed under complementation", SIAM Journal on Computing 17, 1988, pp. 935–938.
R. Szelepcsényi, "The method of forcing for nondeterministic automata", Bulletin of the EATCS 33, 1987, pp. 96–100.

קישורים חיצוניים

גדי אלכסנדרוביץ', משפט אימרמן – מי, מה, כמה ולמה, באתר "לא מדויק", שגיאה: זמן שגוי

הערות שוליים

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

22021101משפט אימרמן

[1] באופן מפורש, האלגוריתם המתואר עונה "כן" על כל קלט שניתן לו, ובפרט אינו אלגוריתם לזיהוי מספר ראשוני.

[2] מושג זה נזקק להגדרה מדויקת אך הוא כולל בתוכו את רובן המוחלט של הפונקציות המתארות סיבוכיות זיכרון. נדרש כי $s(n)\geq \log(n)$

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

[1]

[2]

[3]