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

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

מבוא

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

קשר בין סיבוכיות מקום וסיבוכיות זמן

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

הקשרים בין מחלקות הסיבוכיות השונות

המחלקה PSPACE היא גדולה למדי; למשל, היא מכילה הן את המחלקה NP של הבעיות הניתנות לפתרון אי דטרמיניסטי בזמן פולינומי והן את המחלקה PP של הבעיות הניתנות לפתרון הסתברותי בזמן פולינומי. לא ידוע האם PSPACE=NP או אולי אפילו PSPACE=P, אך ממשפטי ההיררכיה לזיכרון עולה ש-PSPACE שונה מ-L. מכך נובע שלפחות הכלה אחת מתוך השרשרת  חייבת להיות הכלה ממש, אך לא ידוע מהי; הסברה הרווחת היא שכל ההכלות הן הכלות ממש. בשל גודלה של PSPACE, השפות שנמצאות בה אינן נחשבות בהכרח לשפות ש"קל" להכריע; לעומתה, המחלקה L מספקת אפיון שכזה.
בדומה למושג השלמות ב-NP קיים גם מושג דומה של שלמות ב-PSPACE - בעיה היא PSPACE שלמה אם כל שפה ששייכת ל-PSPACE ניתנת לרדוקציה פולינומית אליה. דוגמה לשפה PSPACE שלמה היא השפה TQBF.