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

