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