Consider an oracle $A$ and the language \begin{equation} P(A) = \{x\in \{0, 1\}^{n}: \text{the number of strings in }~A~\text{of length}~|x|~\text{is odd}\}. \end{equation}

I am trying to make sense of the following oracle separation between $\text{PH}$ and $\text{PSPACE}$.

The step that I do not understand is where the author constructs a depth-$d$ circuit of size $2^{n^{c}}$, from a machine $M$ in the $d^{\text{th}}$ level of the polynomial hierarchy (endowed with oracle access to $A$) that runs in time $n^{c}$. Let me quote the relevant part.

On inputs of length $n$, $M$ runs in time $n^{c}$ and makes at most $d$ alternations of universal and existential states along any computation path, where $c$ and $d$ are constants. The computation tree of $M$ on any input can be divided into $d$ levels such that the configurations on any level are either all universal configurations or all existential configurations, and the first level contains only existential configurations.

We can assume without loss of generality that on input $x$, $M$ never queries its oracle on any string that is not the same length as $x$, because these strings are irrelevant in determining whether $x \in P(A)$. If $M$ does so, we can build another machine $N$ that simulates $M$, supplying an arbitrary truth value whenever $M$ would attempt to query the oracle on a string of the wrong length. The machine $N$ must be correct on $n$ if $M$ is.

Now we build a parity circuit $C_{n}$ for each $n$ on which $M$ is correct. The circuit $C_n$ is built from the computation tree of $N$ on input $0^{n}$ and all possible oracles $A$. The gates of the circuit are the configurations of $N$ on input $0^{n}$; there are at most $2^{n^c}$ of these for some constant $c$. The inputs are Boolean variables representing the truth values of $A(y)$, $|y| = n$. There are $2^{n}$ of these. The output gate is the start configuration of $N$. An oracle query just reads the input gate corresponding to the query string.

An existential configuration becomes an $\text{OR}$ gate of unbounded indegree...

A universal configuration becomes an $\text{AND}$ gate of unbounded indegree in a similar fashion. Thus we have flattened each existential and each universal level of the computation tree into a circuit of depth $1$.

The resulting circuits $C_{n}$ are of depth d and size $2^{n^c}$, have $2^{n}$ inputs, and compute the parity of their inputs.

From what I understand, in the definition of $\Sigma_d$ (the $d^{\text{th}}$ level of the polynomial hierarchy), we have $d$ alternations of universal and existential quantifiers, followed by a polynomial time computable predicate. Why does this imply a computation tree that can be divided into $d$ existential-universal levels? I can see how the quantifiers correspond to a $d$-level tree, but after the quantifiers, don't we also need to compute the predicate somehow? The circuit that corresponds to computing the predicate can be an arbitrary polynomial sized circuit --- why can it be divided into $d$ levels?

What is the size and depth of the computation tree for $N$ in the previous question? Is the depth $n^{c}$ or is $n^{c}$ just the size of the computation tree?

I do not understand why $C_n$ has size $2^{n^{c}}$. What is meant by the "number" of possible configurations and why is it relevant in constructing $C_n$? Does the computation tree of $N$ have size $2^{n^{c}}$? Are we somehow trying all configurations in parallel in $C_n$?

Finally, as the author remarks, the input is of length $2^{n}$ and corresponds to the query string. Are our algorithms restricted to use each bit of the input only once? Can we not reuse the bits of the input (by copying them)? If so, won't there be an overhead (the number of gates for copying) that will have to be factor into the size of the circuit?

If there is any better and clearer way to see this reduction (from $\text{PH}$ to circuits), that will also be helpful.

  • 2
    $\begingroup$ The proof you quote is stated in terms of alternating Turing machines (ATMs), which in my opinion is a great way to proceed. $\endgroup$ Aug 10 at 8:46

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.