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?

  • 5
    $\begingroup$ 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$). $\endgroup$ – Joshua Grochow Jun 14 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.