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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

תוכן עניינים

[עריכה] מבוא

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

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

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

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

[עריכה] הגדרה פורמלית

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

הבעייתיות שבהגדרה הנאיבית נעוצה בכך שהן הקלט והן הפלט של המכונה כתובים על הסרט, ולכן נחשבים לחלק מהמדד. למשל, אלגוריתם אשר מקבל מספר ובודק האם ספרתו האחרונה היא 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) תאי זיכרון, שכן בכל צעד ניתן לנצל תא זיכרון חדש אחד לכל היותר.

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

[עריכה] משפט סביץ'

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

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

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

[עריכה] משפט Immerman-Szelepcsényi

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

  • אם \ f(n)\ge\log n היא פונקציית זכרון אז \ \mbox{NSPACE}(f(n))=\mbox{co-NSPACE}(f(n))

[עריכה] משפטי היררכייה

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

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

[עריכה] ראו גם

סיבוכיות זמן

שפות אחרות