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