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