הוכחה: תהי A PSPACE. אזי קיימת מכונה M A כך שקיים פולינום p כך ש-M A מכריעה את A וגם לכל x Σ*, space M A(x) p(…

הוכחה: תהי $A\in PSPACE$. אזי קיימת מכונה $M_A$ כך שקיים פולינום p כך ש$-M_A$ מכריעה את A וגם לכל $x\in Σ*, space_{M_A}(x) \le p(|x|)$. תהי $B\in P^A$. אזי קיימת מכונה $M_B$ עם אורקל דטרמיניסטית כך שקיים פולינום q כך ש$-M_B$ עם אורקל A מכריעה את B וגם לכל $x\in Σ*, time_{M_B}(x) \le q(|x|)$. נגדיר מכונה M באופן הבא: בהינתן קלט x- 1. M תריץ את $M_B$ על x. 2. בכל פעם ש$-M_B$ נשאלת שאילתא עם מחרוזת y, M [לא ברור] את $M_A$ על y. 3. M תחזיר את מה ש$-M_B$ החזירה. M מכריעה את B. ניתוח סיבוכיות מקום: יהי $x\in Σ*$. בריצה של M על x, M דורשת $space_{M_B}(x)$. בנוסף, M מריצה את $M_A$ על אחת מהמחרוזות y [לא ברור] השאילתות באותה הריצה. כל מחרוזת y כזו מקיימת$: |y| \le time_{M_B}(x) \le q(|x|)$ לכן $- space_{M_A}(y) \le p(|y|) \le p(q(|x|))$ אם כן $- space_M(x) \le q(|x|)+p(q(|x|))$ מכיוון שפולינומים סגורים להרכבה, M רצה במקום פולינומי. לכן $B\in PSPACE$. לכן $P^A \subseteq PSPACE$