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

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

מבוא

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

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

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

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

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

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

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

מחלקות סיבוכיות

עבור פונקציה $\ f(n)$ מקובל להשתמש בסימון $\ {\mbox{DSPACE}}(f(n))$ כדי לסמן את אוסף כל בעיות ההכרעה עבורן קיימת מכונת טיורינג דטרמיניסטית שבהינתן קלט באורך $\ n$ פותרת את הבעיה תוך שימוש בזיכרון של לכל היותר $\ f(n)$. לעיתים משתמשים בסימון אסימפטוטי על מנת לפשט את הכתיבה, ומסתפקים בכך שמכונת הטיורינג תפתור את הבעיה בזיכרון $\ O(f(n))$. כלומר - עבור קלטים גדולים מספיק, כמות הזיכרון הנדרשת קטנה מקבוע כלשהו כפול $\ f(n)$.

בצורה דומה מסמנים בתור $\ {\mbox{NSPACE}}(f(n))$ את אוסף בעיות ההכרעה עבורן קיימת מכונת טיורינג לא דטרמיניסטית הפותרת את הבעיה תוך שימוש בזיכרון $\ f(n)$.

בעזרת הסימונים הללו ניתן להגדיר כמה ממחלקות הסיבוכיות המרכזיות בהן עוסקים בחקר סיבוכיות זיכרון: PSPACE, L,NL,EXPSPACE.

• ${\mbox{PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(n^{k})$
• ${\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})$
• $\ {\mbox{L}}={\mbox{DSPACE}}(\log n)$
• $\ {\mbox{NL}}={\mbox{NSPACE}}(\log n)$

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

ניתן להראות כי מתקיים $\ {\mbox{DSPACE}}(f(n))\subseteq {\mbox{DTIME}}(2^{f(n)})$ כלומר, לכל מכונה העובדת בסיבוכיות מקום $\ f(n)$ קיימת מכונה העובדת לכל היותר בסיבוכיות זמן שהיא אקספוננציאלית בסיבוכיות המקום $\ f(n)$ ופותרת את אותה הבעיה.

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

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

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

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

מסקנה נוספת מקשר זה היא שמתקיים תמיד $\ {\mbox{DSPACE}}(f(n))\subseteq R$, כלומר כל בעיה שניתנת לפתרון באמצעות מכונת טיורינג בעלת זיכרון חסום, ניתנת גם להכרעה (כלומר, קיימת מכונת טיורינג שפותרת אותה ועוצרת לכל קלט).

קשר אלמנטרי נוסף בין סיבוכיות זמן וזיכרון הוא $\ {\mbox{DTIME}}(f(n))\subseteq {\mbox{DSPACE}}(f(n))$. קשר זה נובע מכך שמכונה שרצה $\ f(n)$ צעדים אינה מסוגלת לנצל יותר מ-$\ f(n)$ תאי זיכרון, שכן בכל צעד ניתן לנצל תא זיכרון חדש אחד לכל היותר. (ניתן גם להראות תוצאה טובה יותר $\ {\mbox{DTIME}}(f(n))\subseteq {\mbox{DSPACE}}\left({\frac {f(n)}{\log {f(n)}}}\right)$)

משפטים הנוגעים לסיבוכיות זיכרון

משפט סביץ'

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

• אם $\ f(n)\geq \log n$ אז $\ {\mbox{NSPACE}}(f(n))\subseteq {\mbox{DSPACE}}(f^{2}(n))$

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

משפט Immerman-Szelepcsényi

משפט Immerman-Szelepcsényi מראה כי מחלקות סיבוכיות זיכרון אי דטרמיניסטיות סגורות למשלים. בניסוח מדויק:

• אם $\ f(n)\geq \log n$ אז $\ {\mbox{NSPACE}}(f(n))={\mbox{co-NSPACE}}(f(n))$

משפטי היררכיה

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

• אם $\ f(n)\geq \log n$ היא פונקציית זיכרון אז קיימת בעיית הכרעה שניתן להכריע בזיכרון $\ O(f(n))$ אבל לא $\ o(f(n))$.

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

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

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

בדומה למושג השלמות ב-NP קיים גם מושג דומה של שלמות ב-PSPACE - בעיה היא PSPACE שלמה אם כל שפה ששייכת ל-PSPACE ניתנת לרדוקציה פולינומית אליה. דוגמה לשפה PSPACE שלמה היא השפה TQBF.

ראו גם

• סיבוכיות זמן