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

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

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

מסמנים ב-DSPACE(f(n)) את קבוצת הבעיות שנפתרות ע"י מכונת טיורינג דטרמיניסטית המשתמשת עד f(n) תאים של זיכרון עבודה. באופן דומה NSPACE(f(n)) מתארת שימוש בזיכרון עבור מכונות אי-דטרמיניסטיות.

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

משפט סביץ' (Savitch) מקשר בין סיבוכיות מקום דטרמיניסטית לאי-דטרמיניסטית. כתוצאה מזה לא צריך להגדיר מחלקה מיוחדת NPSPACE, מכיוון ש-PSPACE ו-NPSPACE שוות.
משפט Immerman, Szelepcsényi מראה שמחלקות סיבוכיות אי-דטרמיניסטיות סגורות לתוספת המשלים שלהן.

היררכיית הזיכרון אומרת: אם נותנים יותר זיכרון אסימפטוטי, מקבלים יותר בעיות שניתן לפתור. לדוגמה, אם f(n)=o(
log log n) אז DSPACE(f(n)) שווה ל-DSPACE(O(1)), כלומר מספיק זיכרון קבוע. המחלקה DSPACE(O(1)) תואמת לשפות רגולריות.

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

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

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

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

משפט סביץ' אומר שקשר בין זיכרון דטרמיניסטי לאי-דטרמיניסטי קיים. משפט אחר, של Immerman ו-Szelepcsényi, אומר שקבוצות בעיות מסוימות "סגורות" גם אם מחליפים תשובות ל"לא".

PSPACE היא קבוצה גדולה של בעיות שניתן לפתור אם נותנים מספיק זיכרון. היא מכילה גם בעיות מקבוצה שכולם מכירים, כמו NP. דוגמה לבעיית PSPACE־שלמה היא TQBF.