משפט סביץ'

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

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

תוכן עניינים

[עריכה] מבוא

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

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

[עריכה] ניסוח פורמלי

בצורה פורמלית נהוג לראות את הבעיות החישוביות כבעיות של זיהוי שפות פורמליות.

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

בצורה פורמלית, ניסוחו של משפט סביץ' אומר:

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

[עריכה] הוכחה

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

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

[עריכה] משמעות

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

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

[עריכה] לקריאה נוספת

  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.
  • Christos Papadimitriou (1993). Computational Complexity, 1st edition, Addison Wesley. ISBN 0201530821.
שפות אחרות