PSPACE

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

PSPACE מוגדרת כאיחוד כל המחלקות DSPACE(n^k) עבור k טבעי. כלומר, אם אפשר לפתור בעיה במכונה דטרמיניסטית תוך שימוש במקום שהגודלו הוא חזקת פולינום של גודל הקלט, הבעיה שייכת ל-PSPACE.

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

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

קיימת שרשרת הכלות שמציבה את PSPACE בין מחלקות אחרות: NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE. ידוע כי NL ⊊ PSPACE ⊊ EXPSPACE, ומקובל להניח שהשאר חייבות להיות הכלות ממשיות גם כן, אך זו שאלה פתוחה במקרים אחרים.

בעיה B היא PSPACE-שלמה אם B שייכת ל-PSPACE, ולכל בעיה A ב-PSPACE יש רדוקציה בזמן פולינומי מ-A ל-B. בעיות PSPACE-שלמות הן קשות ביותר בתוך המחלקה: פתרון פשוט לאחת מהן ייבא פתרון לכל הבעיות ב-PSPACE. הבעיה הקנונית היא TQBF (True Quantified Boolean Formulas), נוסחאות בוליאניות עם כמתים. גם בעיות משחקים מורחבות, כמו גרסאות כלליות של הקס ואוטלו (Reversi), ידועות כ-PSPACE-שלמות.

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

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

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

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

יש סדר בין מחלקות חשובות כמו P, NP ו-EXPTIME. PSPACE גדולה יותר ממחלקות קטנות יותר, וקטנה ממחלקות שדורשות הרבה יותר זיכרון.

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