# Oracle separation between PH and PSPACE

I am having difficulty understanding the concept and intuition behind this proof. The proof deals with constructing an oracle $$A$$ relative to which $$PH$$ is separated from $$PSPACE$$. I have several questions regarding the proof.

Firstly, what does $$PH^{A} \neq PSPACE^{A}$$ mean? Does this imply that $$PH^{A} \subset PSPACE^{A}$$? We know $$PH$$ is contained in $$PSPACE$$. This theorem shows the existence of an oracle problem that can be solved in $$PSPACE$$ but not in $$PH$$. So, I suspect the statement should hold.

Secondly, it is stated that:

For any language $$A$$, we define an auxiliary language $$Parity_{A}$$ as follows.

Definition 2: $$Parity_{A}$$ = {$$1^{n}$$ | Number of strings in $$A$$ of length n is odd}.

Obviously, for any $$A$$, $$Parity_{A} ∈ PSPACE^{A}$$.

If I understand correctly, $$Parity_{A}$$ is the collection of all strings in $$A$$ of odd length. If that's the case, it is true that $$Parity_{A}$$ can be decided in $$PSPACE^{A}$$. To check if $$x$$ is in $$Parity_{A}$$, we can do the following:

• Check if $$x \in A$$ by querying the oracle $$A$$.
• If $$x \in A$$, compute the parity of $$x$$.
• Accept if $$x \in A$$ and the parity of $$x$$ is odd.

Since $$x = x_{1}x_{2} \ldots x_{n}$$, we can easily compute $$x_{1} \oplus x_{2} \oplus \ldots x_{n}$$ in time polynomial to the input length.

Is this intuition correct? If it is, why is it also not true that $$Parity_{A}$$ can be decided by any language in $$PH^{A}$$, even $$P^{A}$$? What am I missing here?

• First, the proof that $\mathsf{PH} \subseteq \mathsf{PSPACE}$ relativizes, so $\mathsf{PH}^A \subseteq \mathsf{PSPACE}^A$ for any oracle $A$. Second, you are misunderstanding the definition of $Parity_A$. It is $\{1^n : |A \cap \{0,1\}^n| \equiv 0 \pmod{2}\}$, that is, $1^n \in Parity_A$ iff there is an odd number of strings of length $n$ in $A$ (and there are no other strings in $Parity_A$). – Joshua Grochow Jun 14 at 23:22