משפט אימרמן

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

מבוא

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