משפט סביץ'

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

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

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

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

משפט סביץ' הוכח ב־1970 על ידי וולטר סביץ'. המשפט מדבר על כמה זיכרון צריך מחשב כדי לפתור בעיות. מכונת טיורינג היא דרך לחשוב על מחשב פשוט.

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

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

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